5931. 用邮票贴满网格图

题目描述

 

 

 

 

解题思路

查找标志为0的点，尝试以该点为邮票的左上角，直到尝试为以该点为邮票的右下角.如果能放邮票，并覆盖该为0 的点，则把覆盖的点标志为2。如果不能，直接返回false.

解题代码

public class solution5931 {private int stampHeight;private int stampWidth;public static void main(String[] args) {int[][] a1 = new int[][]{{1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}};int[][] a2 = new int[][]{{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};int[][] a3 = new int[][]{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 1}};boolean b1 = new solution5931().possibleToStamp(a1, 4, 3);boolean b2 = new solution5931().possibleToStamp(a2, 2, 2);boolean b3 = new solution5931().possibleToStamp(a3, 3, 3);System.out.println(b1);System.out.println(b2);System.out.println(b3);}public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {this.stampHeight = stampHeight;this.stampWidth = stampWidth;int n = grid.length;int n1 = grid[0].length;//遍历所有标志为0的点for (int i = 0; i < n; i++) {for (int j = 0; j < n1; j++) {if (grid[i][j] == 0) {//此地必须要放//尝试以该点为邮票的左上角，直到尝试为以该点为邮票的右下角boolean b = false;int x = -1, y = -1;for (int k = i; k >= Math.max(0, i - stampHeight + 1); k--) {for (int l = j; l >= Math.max(0, j - stampWidth + 1); l--) {boolean c = check(grid, k, l);if (c) {// 检测结果表明，此票放(k，l)这个位置能够满足要求，并能覆盖住(i1,j1)b = true;x = k;y = l;break;}}if (b) {break;}}if (b) {// 成功在以(x,y)为左上角的地方，放下邮票，把所有被该邮票占据的地方，填上2for (int x1 = x; x1 < x + stampHeight; x1++) {for (int y1 = y; y1 < y + stampWidth; y1++) {grid[x1][y1] = 2;}}} else {// (i1,j1)这个位置无法放邮票return false;}}}}return true;}private boolean check(int[][] grid, int i1, int j1) {if (i1 + stampHeight > grid.length) {// 越界return false;}if (j1 + stampWidth > grid[0].length ) {// 越界return false;}for (int i = i1; i < i1 + stampHeight; i++) {for (int j = j1; j < j1 + stampWidth; j++) {if (grid[i][j] == 1) {// 禁放return false;}}}return true;}}

解题结果

非常遗憾的是，没能在周赛当中写出结果。第二天重新思考后得出结果，这是目前是我离做出周赛全部四题最近的一次了。继续加油！！！！

总结

以上是生活随笔为你收集整理的Leetcode69场双周赛-第四题5931. 用邮票贴满网格图的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。