wordpress 只备份文章,郑州网站优化公司排名,湖州住房和城乡建设局网站,搜索引擎优化搜索优化文章目录1. 题目2. 解题1. 题目
给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。 同时给你两个二维整数数组 guards 和 walls #xff0c;其中 guards[i] [rowi, coli] 且 walls[j] [rowj, colj] #xff0c;分别表示第 i 个警卫和第 j 座墙所在的位置。
一…
文章目录1. 题目2. 解题1. 题目
给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。 同时给你两个二维整数数组 guards 和 walls 其中 guards[i] [rowi, coli] 且 walls[j] [rowj, colj] 分别表示第 i 个警卫和第 j 座墙所在的位置。
一个警卫能看到 4 个坐标轴方向即东、南、西、北的 所有 格子除非他们被一座墙或者另外一个警卫 挡住 了视线。 如果一个格子能被 至少 一个警卫看到那么我们说这个格子被 保卫 了。
请你返回空格子中有多少个格子是 没被保卫 的。
示例 1
输入m 4, n 6,
guards [[0,0],[1,1],[2,3]],
walls [[0,1],[2,2],[1,4]]
输出7
解释上图中被保卫和没有被保卫的格子分别用红色和绿色表示。
总共有 7 个没有被保卫的格子所以我们返回 7 。示例 2
输入m 3, n 3,
guards [[1,1]],
walls [[0,1],[1,0],[2,1],[1,2]]
输出4
解释上图中没有被保卫的格子用绿色表示。
总共有 4 个没有被保卫的格子所以我们返回 4 。提示
1 m, n 10^5
2 m * n 10^5
1 guards.length, walls.length 5 * 10^4
2 guards.length walls.length m * n
guards[i].length walls[j].length 2
0 rowi, rowj m
0 coli, colj n
guards 和 walls 中所有位置 互不相同 。来源力扣LeetCode 链接https://leetcode.cn/problems/count-unguarded-cells-in-the-grid 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
按题意模拟
class Solution {
public:int countUnguarded(int m, int n, vectorvectorint guards, vectorvectorint walls) {vectorvectorint g(m, vectorint(n,0));vectorvectorint dir {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};int police 1, wall 2, mark 3;for(auto p : guards)g[p[0]][p[1]] police;for(auto w : walls)g[w[0]][w[1]] wall;for(int i 0; i m; i){for(int j 0; j n; j){if(g[i][j]police){ for(int k 0; k 4; k){int nx i, ny j;while(1){nx dir[k][0], ny dir[k][1];if(nx0 nxm ny0 nyn){if(g[nx][ny]police || g[nx][ny]wall)break;g[nx][ny] mark;}elsebreak;}}}}}int ans 0;for(int i 0; i m; i){for(int j 0; j n; j){if(g[i][j]0)ans;}}return ans;}
};484 ms 150.4 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
