思路

就是力扣85题最大矩阵和的思路。
把障碍点设为1，非障碍点设为0，跑一遍求最大矩阵的代码，同时记录最大矩阵面积为eara，长和宽最大值maxv和最小值minv，
如果eara > c * d && maxv > max(c, d) && minv > min(c, d), 返回YES，否则NO

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 160;

int t, n, m, k, c, d;

char mat[N][N];
int help(vector<int>& a,int &minv, int& maxv) {
    int n = a.size();

    int tt = 0;
    vector<int> stk(n + 10), left(n), right(n);

    for (int i = 0; i < n; ++ i) {
        while (tt && a[stk[tt]] >= a[i]) tt--;

        if (tt) left[i] = stk[tt];
        else left[i] = -1;

        stk[++ tt] = i;
    }

    tt = 0;

    for (int i = n - 1; ~i; -- i) {
        while (tt && a[stk[tt]] >= a[i]) tt--;

        if (tt) right[i] = stk[tt];
        else right[i] = n;

        stk[++ tt] = i;
    }

    int ret = 0;
    for (int i = 0; i < n; ++ i) {

        int erea = (right[i] - left[i] - 1) * a[i];
        if (ret < erea) {
            ret = erea;
            minv = min({a[i], right[i] - left[i] - 1});
            maxv = max({a[i], right[i] - left[i] - 1});
        }
    }

    return ret;
}
int main() {
    cin >> t;
    while (t -- ) {
        cin >> n >> m >> k;
        int x, y;
        memset(mat, 0, sizeof mat);
        for (int i = 1; i <= k ; ++i ) {
            cin >> x >> y;
            mat[x - 1][y - 1] = '1';
        }
        cin >> c >> d;

        vector<int> a(m + 1);
        int ret = 0;
        bool f = false;
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                if (mat[i][j] == '1')
                    a[j] = 0;
                else
                    a[j] ++ ;
            }
            int minv = 0, maxv = 0;
            int ans = help(a, minv, maxv);

            if (ans >= c * d && minv >= (min(c, d)) && (maxv >= (max(d,c)))) {
                f = true;
                break;
            }

        }
        if (f)
            cout << "YES" <<endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

#抄的dragonlogin的代码 最玄学的是 py35不过py36过了
t = int(input())
def helper(a, maxv, minv):
    n = len(a)
    tt = 0
    stack = [0]*(n+10)
    left, right = [0]*n, [0]*n
    for i in range(n):
        while tt and a[stack[tt]]>=a[i]:
            tt-=1
        if tt:
            left[i] = stack[tt]
        else:
            left[i] = -1
        tt+=1
        stack[tt]=i
    for i in range(n-1, -1, -1):
        while tt and a[stack[tt]]>=a[i]:
            tt-=1
        if tt:
            right[i] = stack[tt]
        else:
            right[i] = n
        tt+=1
        stack[tt]=i
    ret = 0
    
    for i in range(n):
        area = (right[i]-left[i]-1)*a[i]
        if ret<area:
            ret = area
            minv = min(a[i], right[i]-left[i]-1)
            maxv = max(a[i], right[i]-left[i]-1)
    return ret, maxv, minv

for i in range(t):
    n, m, k = map(int, input().split())
    dp = [[0]*m for i in range(n)]
    for j in range(k):
        x, y = map(int, input().split())
        dp[x-1][y-1] = -1
    c, d = map(int, input().split())
    a = [0]*(m) #这个地方写成m+1不过
    flag = False
    for x1 in range(n):
        for y1 in range(m):
            if dp[x1][y1] == -1:
                a[y1]=0
            else:
                a[y1]+=1
        ans, maxv, minv = helper(a, 0, 0)
        if ans>=c*d and maxv>=max(c,d) and minv>=min(c,d):
            flag = True
    if flag:
        print('YES')
    else:
        print('NO')
            

放置货物 csdn

结合🌰来讲，货物的大小为c=3,d=6。
考虑货物左上角的坐标x,y，那么对于每一个障碍物，x,y不能落在左上的c=3,d=6的矩形范围。
对每个障碍物对应的矩形做标记，如果结束后存在未被标记的点则存在可行的x,y来放下货物。

package main

import "fmt"

func generateFlagMatrix(n,m int) (matrix [][]bool) {
    for i:=0;i<n;i++{
        line:=make([]bool,m)
        matrix= append(matrix, line)
    }
    return
}

func min(a,b int) int {
    if a>b{
        return b
    }else {
        return a
    }
}

func max(a,b int) int {
    if a<b{
        return b
    }else {
        return a
    }
}

type point struct {
    x int
    y int
}

//              广场大小，货物大小
func setFlagArea(n,m,x,y int,pos point,invalid [][]bool){
    u:=max(1,pos.x-x+1)
    l:=max(1,pos.y-y+1)
    for i:=u;i<=pos.x;i++{
        for j:=l;j<=pos.y;j++{
            invalid[i-1][j-1]=true
        }
    }
}

func verify(invalid [][]bool, x,y int) bool {
    for i:=0;i< len(invalid)-x+1;i++{
        for j:=0;j<len(invalid[0])-y+1;j++{
            if invalid[i][j]==false{
                return true
            }
        }
    }
    return false
}

func main() {
    var t,m,n,k,x,y int
    fmt.Scan(&t)
    for i:=0;i<t;i++{
        fmt.Scan(&n,&m,&k)
        //默认值为false，表示可用，true表示不可用
        invalid:=generateFlagMatrix(n,m)
        var blocks []point
        for j:=0;j<k;j++{
            fmt.Scan(&x,&y)
            blocks= append(blocks, point{x,y})
        }
        fmt.Scan(&x,&y)
        for _,p:=range blocks{
            setFlagArea(n,m,x,y,p,invalid)
        }
        if verify(invalid,x,y){
            fmt.Println("YES")
        }else{
            fmt.Println("NO")
        }
    }
}

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);          
        // 几组数据
        int size = sc.nextInt(); 
        while(size != 0){
            // 广场长和宽
            int n = sc.nextInt();
            int m = sc.nextInt();
            // 二维数组，如果当前位置可用为 false，有障碍物为 true
            boolean[][] matrix = new boolean[n][m];
            int obstacle = sc.nextInt();
            for (int i = 0; i < obstacle; i++) {
                // 障碍物的位置
                int row = sc.nextInt() - 1;
                int col = sc.nextInt() - 1;
                matrix[row][col] = true;
            }
            // 货物长和宽
            int c = sc.nextInt();
            int d = sc.nextInt();
            boolean flag = canPlace(matrix,obstacle,c,d);
            if(flag) System.out.println("YES");
            else System.out.println("NO");
            --size;
        }
    }
       /**
         * 一层一层遍历，如果当前位置为false，表示位置可用，则 dp[j] += 1,如果不可用
         * 则直接为 0.
         */
    public static boolean canPlace(boolean[][] palce, int k, int length, int width){

        int n = palce.length, m = palce[0].length;
        if(k == 0) return n >= length && width >= m;
        boolean flag = false;
        int[] dp = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(!palce[i][j]) dp[j] += 1;
                else dp[j] = 0;
            }
            flag = canPlace(dp,length,width);
            // 如果存在，则提前结束返回
            if(flag) break;
        }
        return flag;
    }


    /**
     *  最大面积稍稍变形
     *    求当前数组能组成的最大的长和宽
     */
    public static boolean canPlace(int[] heights, int c, int d){
        // 单调栈
        int[] stack = new int[heights.length + 1];
        stack[0] = -1;
        int top = 0;
        for (int i = 0; i < heights.length; i++) {

            while(top != 0 && heights[i] < heights[stack[top]]){
                if(heights[stack[top--]] >= c && i - stack[top] - 1 >= d) return true;
            }
            stack[++top] = i;
        }
        while(top != 0) {
            if(heights[stack[top--]] >= c && heights.length - 1 - stack[top] >= d) return true;
        }
        return false;
    }
}

最大矩阵思路：
O(M*N)
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int numOfCase = in.nextInt();
        
        for (int a = 0; a < numOfCase;  a++) {
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            int[][] grid = new int[n][m];
            for (int i = 0 ; i < n; i++) {
                Arrays.fill(grid[i],1);
            }
            for (int i = 0; i < k; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                grid[x-1][y-1] = 0;
            }
            int c = in.nextInt();
            int d = in.nextInt();
            
            int[] height = new int[m];
            int[] left = new int[m];
            int[] right = new int[m];
            
            Arrays.fill(right, m);
            
            boolean found = false;
            
            for (int i = 0; i < n; i++) {
                int curLeft = 0, curRight = m;
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 1) height[j]++;
                    else height[j] = 0;
                }
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 1) left[j] = Math.max(left[j],curLeft);
                    else {left[j] = 0; curLeft = j+1;}
                }
                for (int j = m-1; j >= 0; j--) {
                    if (grid[i][j] == 1) right[j] = Math.min(right[j],curRight);
                    else {right[j] = m; curRight = j;}
                }
                for (int j = 0; j < m; j++) {
                    int cc = right[j] - left[j], dd = height[j];
                    if (cc*dd >= c*d &&(cc >= c && dd >= d )  
                         || (cc >= d && dd >= c) ) found = true;
                }
                if (found) {
                    System.out.println("YES");
                    break;
                }
            }
            if (!found) {
                 System.out.println("NO");
            }

        }
        
    }
}

#include <vector>
#include <iostream>

using namespace std;

int t;
int n, m, k;

bool judge(vector<vector<bool>> &v, int ni, int nj, int c, int d) {
    for (int i = 0; i < c; i++) {
        if (ni + i >= n) return false;
        for (int j = 0; j < d; j++) {
            if (nj + j >= m) return false;
            if (v[ni + i][nj + j]) {
                
                // 遍历到一个障碍后，将起点和障碍之内的点全部不可能为结果的起点
                // 因此全部置为障碍
                for (int p = 0; p <= i; p++) {
                    for (int k = 0; k <= j; k++) {
                        v[ni + p][nj + k]= true;
                    }
                }
                
                return false;
            }
        }
    }
    
    return true;
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    
    cin >> t;
    
    while (t--) {
        cin >> n >> m >> k;
        vector<vector<bool>> v(n, vector<bool>(m, false));
        while (k--) {
            int a, b;
            cin >> a >> b;
            v[a - 1][b - 1] = true;
        }
        
        int c, d;
        cin >> c >> d;
        
        bool flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!v[i][j] && judge(v, i, j, c, d)) {
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        
        if (flag) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
        
    }
    
    return 0;
}