小易有一个体积巨大的货物,具体来说,是个在二维平面上占地的货物。
小易有一个的广场,想把货物放在这个广场上。不幸的是,广场上已经有了一些障碍物,障碍物所在的格子不能放置你的货物。小易现在想知道能否成功地放置货物。
第一行数字t,表示有t组数据。
对于每一组数据,第一行三个数字n,m,k,表示广场的大小和障碍物的个数。接下来k行,每行两个数x,y,表示一个障碍物的坐标。接下来一行两个数c,d,表示货物的大小。,
对于每组数据,输出"YES"或者"NO"表示货物是否可以被放置。
2 3 3 1 1 1 2 2 3 3 1 2 2 2 2
YES NO
就是力扣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; }
import java.util.Scanner; public class Main { private static Scanner sc; public static void main(String[] args) { sc = new Scanner(System.in); int t = sc.nextInt();//组数 for (int a = 0; a < t; a++) { int n = sc.nextInt();//广场长(宽) int m = sc.nextInt();//广场长(宽) int k = sc.nextInt();//障碍物个数 int[][] grid = new int[n + 10][m + 10]; for (int i = 0; i < k; i++) {//填入障碍物坐标 grid[sc.nextInt()][sc.nextInt()] = 1; } for (int row = 1; row < n; row++) { for (int col = 1; col < m; col++) { grid[row][col] += grid[row - 1][col] + grid[row][col - 1] - grid[row - 1][col - 1]; } } int c = sc.nextInt();//货物长(宽) int d = sc.nextInt();//货物长(宽) boolean findPosition = false; for (int row = 1; row < n - c + 1; row++) { for (int col = 1; col < m - d + 1; col++) { int ok = grid[row + c - 1][col + d - 1] - grid[row + c - 1][col - 1] - grid[row - 1][col + d - 1] + grid[row - 1][col - 1]; if (ok == 0) { System.out.println("YES"); findPosition = true; break; } } if (findPosition) { break; } } if (!findPosition) { System.out.println("NO"); } } } }
#抄的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')
结合🌰来讲,货物的大小为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<bits/stdc++.h> using namespace std; int dp[1005][1005]; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int T; cin>>T; while(T--){ int n,m,k,c,d; cin>>n>>m>>k; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ dp[i][j]=1; } } for(int i=0;i<k;++i){ cin>>c>>d; dp[c][d]=0; } for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ if(dp[i][j]>0){ dp[i][j]=dp[i-1][j]+1; } } } cin>>c>>d; int now=0,ma=0; bool flag=false; for(int i=1;i<=n;++i){ now=0; for(int j=1;j<=m;++j){ if(dp[i][j]>=d){ now++; ma=max(ma,now); }else{ now=0; } } } if(ma>=c)flag=true; now=0,ma=0; for(int i=1;i<=n;++i){ now=0; for(int j=1;j<=m;++j){ if(dp[i][j]>=c){ now++; ma=max(ma,now); }else{ now=0; } } } if(ma>=d)flag=true; if(flag)cout<<"YES"<<'\n'; else cout<<"NO"<<'\n'; } }
#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; }