北京网站设计公司最近的疫情情况最新消息

🔗 https://leetcode.com/problems/count-unguarded-cells-in-the-grid

题目

• 给出一个 m x n 的二维表格，格子上有士兵 guard，有墙 wall
• 士兵可以盯上他上下左右所有的格子，碰到墙的格子就停止
• 返回没有被士兵盯到的格子的数量

思路

• 二维数组模拟处理即可，对于每一个士兵，不断占领四个方向的格子，直到碰到士兵，或者墙，就停止

• 最后统计没有被占领的格子的数量

• 看到过一个比较巧妙的四个方向遍历的预处理，即设置一个长度为 4 的数组，表达四个方向，四个方向可以表达为：

          dir.push_back({-1, 0});dir.push_back({0, -1});dir.push_back({1, 0});dir.push_back({0, 1});
  

代码

class Solution {
public:int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {// initbool mark[m][n], mark_wall[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {mark[i][j] = mark_wall[i][j] = false;}}for (auto& wall : walls) {int r = wall[0], c = wall[1];mark_wall[r][c] = true;mark[r][c] = true;}for (auto& guard : guards) {int r = guard[0], c = guard[1];mark_wall[r][c] = true;mark[r][c] = true;}//iteratorvector<vector<int>> dir;dir.push_back({-1, 0});dir.push_back({0, -1});dir.push_back({1, 0});dir.push_back({0, 1});for (auto& guard : guards) {int r = guard[0], c = guard[1];//printf("guard r %d c %d\n", r, c);for (int i = 0; i < dir.size(); i++) {int cur_r = r + dir[i][0], cur_c = c + dir[i][1];//printf("check r %d c %d\n", r, c);while (cur_r >= 0 && cur_r < m &&cur_c >= 0 && cur_c < n && mark_wall[cur_r][cur_c] == false) {mark[cur_r][cur_c] = true;cur_r += dir[i][0];cur_c += dir[i][1];//printf("check r %d c %d\n", r, c);}}}// countint ans = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (mark[i][j] == false) ans++;}}return ans;}
};