统计网格图中没有被保卫的格子数 图解题解

这道题到底在问什么

输入

m=4, n=5, guards=[[0,0],[2,3]], walls=[[0,2],[2,1],[3,3]]

输出

7

输入

m=3, n=3, guards=[[1,1]], walls=[[0,1],[1,0],[2,1],[1,2]]

输出

4

最优解：一步一步想明白

1. 3记牢这一句:警卫和墙都是 2 号挡板,视线沿四个方向推进,遇到挡板或边界就停,沿途空格标 1。最后还是 0 的空格就是答案。下面把网格铺开,一个警卫一个警卫地射。
2. 4橙=警卫 红=墙 灰=空格这是初始的 4 行 5 列网格。橙色的两格是警卫,分别在 (0,0) 和 (2,3);红色的三格是墙,在 (0,2)、(2,1)、(3,3)。剩下的灰色格子就是 15 个空格,现在一个都还没被照到。警卫和墙在算法里都记成 2,是视线撞上就得停的硬挡板。
3. 5当前警卫 (0,0)从第一个警卫开始。把镜头对准 (0,0) 这个警卫,它要朝上、右、下、左四个方向依次射出视线。约定按上右下左的顺序走,每个方向都从警卫脚下往外一步一步推进,把碰到的空格点亮成绿色,直到撞墙、撞另一个警卫或者射出边界才收手。
4. 6向上越界警卫 (0,0) 紧贴着网格的边,向上第一步就出界了,这个方向一格都照不到,直接跳过。
5. 7警卫 (0,0) 向右警卫 (0,0) 的视线向右推进一步,来到 (0,1)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 1。视线还没撞到挡板,接着往右看下一格。
6. 8向右撞挡板视线继续向右走,下一格 (0,2) 是一堵墙,值是 2,是硬挡板。视线被它挡住,(0,2) 后面的格子这条射线就照不到了,停线。
7. 9警卫 (0,0) 向下警卫 (0,0) 的视线向下推进一步,来到 (1,0)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 2。视线还没撞到挡板,接着往下看下一格。
8. 10警卫 (0,0) 向下警卫 (0,0) 的视线向下推进一步,来到 (2,0)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 3。视线还没撞到挡板,接着往下看下一格。
9. 11警卫 (0,0) 向下警卫 (0,0) 的视线向下推进一步,来到 (3,0)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 4。视线还没撞到挡板,接着往下看下一格。
10. 12向下越界向下这条射线一直照到网格边上,再往下就出界了,没有格子可照,这条射线到此为止。刚才点亮的几格记录在右边面板里。
11. 13向左越界警卫 (0,0) 紧贴着网格的边,向左第一步就出界了,这个方向一格都照不到,直接跳过。
12. 14警卫 (0,0) 完成警卫 (0,0) 的四个方向都射完了。它照亮了自己右边一格和下边一列,目前已保卫的空格数是 4。接着处理下一个警卫。
13. 15当前警卫 (2,3)轮到第二个警卫。把镜头对准 (2,3) 这个警卫,它要朝上、右、下、左四个方向依次射出视线。约定按上右下左的顺序走,每个方向都从警卫脚下往外一步一步推进,把碰到的空格点亮成绿色,直到撞墙、撞另一个警卫或者射出边界才收手。
14. 16警卫 (2,3) 向上警卫 (2,3) 的视线向上推进一步,来到 (1,3)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 5。视线还没撞到挡板,接着往上看下一格。
15. 17警卫 (2,3) 向上警卫 (2,3) 的视线向上推进一步,来到 (0,3)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 6。视线还没撞到挡板,接着往上看下一格。
16. 18向上越界向上这条射线一直照到网格边上,再往上就出界了,没有格子可照,这条射线到此为止。刚才点亮的几格记录在右边面板里。
17. 19警卫 (2,3) 向右警卫 (2,3) 的视线向右推进一步,来到 (2,4)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 7。视线还没撞到挡板,接着往右看下一格。
18. 20向右越界向右这条射线一直照到网格边上,再往右就出界了,没有格子可照,这条射线到此为止。刚才点亮的几格记录在右边面板里。
19. 21向下撞挡板警卫 (2,3) 向下第一步就是 (3,3),那里正好是一堵墙,值为 2。视线一出门就被挡死,这个方向一格都照不到。
20. 22警卫 (2,3) 向左警卫 (2,3) 的视线向左推进一步,来到 (2,2)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 8。视线还没撞到挡板,接着往左看下一格。
21. 23向左撞挡板视线继续向左走,下一格 (2,1) 是一堵墙,值是 2,是硬挡板。视线被它挡住,(2,1) 后面的格子这条射线就照不到了,停线。
22. 24警卫 (2,3) 完成警卫 (2,3) 的四个方向都射完了。两个警卫都处理完了,网格里所有被保卫的空格都已经变绿,一共 8 个。下面把剩下的灰格数出来。
23. 25答案 = 7两个警卫都射完了,现在数账。一共 15 个空格,被视线照到、变绿的有 8 个,剩下没被任何视线扫到的空格有 7 个,我把它们标成蓝色。像 (0,4)、(1,1) 这些格子,四周的视线要么被墙拦下、要么根本射不到,所以谁也看不见它们。15 减 8 等于 7,这就是没被保卫的格子数。
24. 26答案 = 7回放一遍。橙色是警卫,红色是墙,绿色是被视线照到的空格,蓝色这 7 格是没被保卫的。仔细看会发现,警卫 (0,0) 向右的视线被墙 (0,2) 挡住,所以右上角一带照不全;警卫 (2,3) 向下一步就撞上墙 (3,3),底下那格也没人管。挡板决定了视线的边界,数出蓝色格子共 7 个,答案就是它。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def countUnguarded(
        self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]
    ) -> int:
        g = [[0] * n for _ in range(m)]
        for i, j in guards:
            g[i][j] = 2
        for i, j in walls:
            g[i][j] = 2
        dirs = (-1, 0, 1, 0, -1)
        for i, j in guards:
            for a, b in pairwise(dirs):
                x, y = i, j
                while 0 <= x + a < m and 0 <= y + b < n and g[x + a][y + b] < 2:
                    x, y = x + a, y + b
                    g[x][y] = 1
        return sum(v == 0 for row in g for v in row)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        int g[m][n];
        memset(g, 0, sizeof(g));
        for (auto& e : guards) {
            g[e[0]][e[1]] = 2;
        }
        for (auto& e : walls) {
            g[e[0]][e[1]] = 2;
        }
        int dirs[5] = {-1, 0, 1, 0, -1};
        for (auto& e : guards) {
            for (int k = 0; k < 4; ++k) {
                int x = e[0], y = e[1];
                int a = dirs[k], b = dirs[k + 1];
                while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && g[x + a][y + b] < 2) {
                    x += a;
                    y += b;
                    g[x][y] = 1;
                }
            }
        }
        int ans = 0;
        for (auto& row : g) {
            ans += count(row, row + n, 0);
        }
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        int[][] g = new int[m][n];
        for (int[] e : guards) {
            g[e[0]][e[1]] = 2;
        }
        for (int[] e : walls) {
            g[e[0]][e[1]] = 2;
        }
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int[] e : guards) {
            for (int k = 0; k < 4; ++k) {
                int x = e[0], y = e[1];
                int a = dirs[k], b = dirs[k + 1];
                while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && g[x + a][y + b] < 2) {
                    x += a;
                    y += b;
                    g[x][y] = 1;
                }
            }
        }
        int ans = 0;
        for (int[] row : g) {
            for (int v : row) {
                if (v == 0) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问