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

既不是警卫墙、又没被看到的空格有几个

给一张 m 行 n 列的网格，上面放了若干警卫和墙。每个警卫朝上下左右四个方向看，视线一直延伸，直到撞上一堵墙或另一个警卫才停下，沿途空格就算被保卫。问既不是警卫、也不是墙、又没被任何警卫看到的空格有几个。题面例子 m=4、n=5，警卫在 (0,0) 和 (2,3)，墙在 (0,2)、(2,1)、(3,3)，答案是 7。

站在每个空格反着找警卫，慢在哪

一种想法是站在每个空格上，朝四个方向各望出去，看沿途有没有警卫、路上有没有墙挡着。这能得出答案，可 m·n 个空格每个都要往外扫四条线，同一段空地被反复走，一多就拖。既然视线本来就是从警卫发出的，不如让警卫主动往外射：一条视线扫过的空格顺手全标上，每段空地只走一遍。

让警卫主动射线，遇挡板就收手

把网格开成一张表，先把每个警卫、每堵墙都记成挡板值 2。再对每个警卫沿四个方向发射线。射线，就是从警卫脚下沿一个方向一路走到底：每往前一步，只要下一格还在网格里、又不是挡板，就把它标成 1、记作被看守，继续推进；一旦下一格是墙、是另一个警卫或已越出边界，这条线立刻收住。所有警卫都射完，表里还是 0 的格子就是没被保卫的空格，数出来即答案。

四个方向怎么编码，每步为何先判边界

四个方向用一个小技巧编码：方向数组写成 (-1,0,1,0,-1)，相邻两两配对——(-1,0) 是上、(0,1) 是右、(1,0) 是下、(0,-1) 是左，正好凑齐四个偏移，省去四段几乎一样的代码。推进时守住一条：每落脚之前先看下一格在不在界内、是不是挡板，两个条件都过才前进、才标 1。先判界再走，警卫贴边时向外一步就出界、循环自然拦下，不会越出数组。

拿题面这张 4 行 5 列网格亲手射一遍

先把 (0,0)、(2,3) 两个警卫和 (0,2)、(2,1)、(3,3) 三堵墙都置成 2。轮到警卫 (0,0)：向上一步就出界、跳过；向右到 (0,1) 标 1，再走一步撞上墙 (0,2) 停；向下依次标 (1,0)、(2,0)、(3,0) 到底；向左出界跳过——它照亮了 4 格。再轮到警卫 (2,3)：向上标 (1,3)、(0,3) 到顶；向右标 (2,4) 到边；向下第一步就是墙 (3,3)、直接停；向左标 (2,2)、再走一步撞上墙 (2,1) 停——又照亮 4 格。八格标完，整张表里还是 0 的格子共 7 个，就是没被保卫的空格。

撞上挡板还往后标，答案就偏小

复杂度上，开表、射线标记、最后数 0 各遍历一遍；警卫和墙把每行每列切成若干段空地，每段最多被两侧警卫各扫一次，单格在横竖两个方向都只被常数次经过，时间 O(m·n)。那张 m·n 的状态表是主要开销，没有额外递归或队列，空间 O(m·n)。

最容易出岔的是收线时机：视线撞到值为 2 的格子必须当场停，多标一格就把墙后本看不到的空格算进去，答案偏小；只把警卫记成挡板、忘了墙也挡视线，视线便会穿墙而过，凭空多标一片。边界也要想清：警卫被墙贴身围住时四个方向一步都迈不出，答案就是全部空格；整张网格一个空格都没有、或唯一那个空格恰好被照到，答案都是 0。

Python

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)

C++

#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;
    }
};

Java

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;
    }
}