题目描述
思路解析
一句话答案：LeetCode 2257 统计网格中没有被保卫的格子数：射线标记法，把警卫和墙都当挡板，每个警卫朝四个方向逐格标『被看守』、遇挡板或边界停，最后数仍是空的格子，时间 O(m·n)。
既不是警卫墙、又没被看到的空格有几个
给一张 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。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:警卫和墙都是 2 号挡板,视线沿四个方向推进,遇到挡板或边界就停,沿途空格标 1。最后还是 0 的空格就是答案。下面把网格铺开,一个警卫一个警卫地射。
初始网格 · 摆好警卫和墙：这是初始的 4 行 5 列网格。橙色的两格是警卫,分别在 (0,0) 和 (2,3);红色的三格是墙,在 (0,2)、(2,1)、(3,3)。剩下的灰色格子就是 15 个空格,现在一个都还没被照到。警卫和墙在算法里都记成 2,是视线撞上就得停的硬挡板。
选中警卫 (0,0) · 准备射四个方向：从第一个警卫开始。把镜头对准 (0,0) 这个警卫,它要朝上、右、下、左四个方向依次射出视线。约定按上右下左的顺序走,每个方向都从警卫脚下往外一步一步推进,把碰到的空格点亮成绿色,直到撞墙、撞另一个警卫或者射出边界才收手。
向上射线 · 到边界停：警卫 (0,0) 紧贴着网格的边,向上第一步就出界了,这个方向一格都照不到,直接跳过。
向右射线 · 照亮 (0,1)：警卫 (0,0) 的视线向右推进一步,来到 (0,1)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 1。视线还没撞到挡板,接着往右看下一格。
向右射线 · 撞墙停：视线继续向右走,下一格 (0,2) 是一堵墙,值是 2,是硬挡板。视线被它挡住,(0,2) 后面的格子这条射线就照不到了,停线。
向下射线 · 照亮 (1,0)：警卫 (0,0) 的视线向下推进一步,来到 (1,0)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 2。视线还没撞到挡板,接着往下看下一格。
向下射线 · 照亮 (2,0)：警卫 (0,0) 的视线向下推进一步,来到 (2,0)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 3。视线还没撞到挡板,接着往下看下一格。
向下射线 · 照亮 (3,0)：警卫 (0,0) 的视线向下推进一步,来到 (3,0)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 4。视线还没撞到挡板,接着往下看下一格。
向下射线 · 到边界停：向下这条射线一直照到网格边上,再往下就出界了,没有格子可照,这条射线到此为止。刚才点亮的几格记录在右边面板里。
向左射线 · 到边界停：警卫 (0,0) 紧贴着网格的边,向左第一步就出界了,这个方向一格都照不到,直接跳过。
警卫 (0,0) 四向射完：警卫 (0,0) 的四个方向都射完了。它照亮了自己右边一格和下边一列,目前已保卫的空格数是 4。接着处理下一个警卫。
选中警卫 (2,3) · 准备射四个方向：轮到第二个警卫。把镜头对准 (2,3) 这个警卫,它要朝上、右、下、左四个方向依次射出视线。约定按上右下左的顺序走,每个方向都从警卫脚下往外一步一步推进,把碰到的空格点亮成绿色,直到撞墙、撞另一个警卫或者射出边界才收手。
向上射线 · 照亮 (1,3)：警卫 (2,3) 的视线向上推进一步,来到 (1,3)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 5。视线还没撞到挡板,接着往上看下一格。
向上射线 · 照亮 (0,3)：警卫 (2,3) 的视线向上推进一步,来到 (0,3)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 6。视线还没撞到挡板,接着往上看下一格。
向上射线 · 到边界停：向上这条射线一直照到网格边上,再往上就出界了,没有格子可照,这条射线到此为止。刚才点亮的几格记录在右边面板里。
向右射线 · 照亮 (2,4)：警卫 (2,3) 的视线向右推进一步,来到 (2,4)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 7。视线还没撞到挡板,接着往右看下一格。
向右射线 · 到边界停：向右这条射线一直照到网格边上,再往右就出界了,没有格子可照,这条射线到此为止。刚才点亮的几格记录在右边面板里。
向下射线 · 撞墙停：警卫 (2,3) 向下第一步就是 (3,3),那里正好是一堵墙,值为 2。视线一出门就被挡死,这个方向一格都照不到。
向左射线 · 照亮 (2,2)：警卫 (2,3) 的视线向左推进一步,来到 (2,2)。这一格原来是空的,现在被视线扫到,标成 1、点亮成绿色,表示它被保卫了。已保卫的空格数变成 8。视线还没撞到挡板,接着往左看下一格。
向左射线 · 撞墙停：视线继续向左走,下一格 (2,1) 是一堵墙,值是 2,是硬挡板。视线被它挡住,(2,1) 后面的格子这条射线就照不到了,停线。
警卫 (2,3) 四向射完：警卫 (2,3) 的四个方向都射完了。两个警卫都处理完了,网格里所有被保卫的空格都已经变绿,一共 8 个。下面把剩下的灰格数出来。
数一数 · 还是灰的空格就是答案：两个警卫都射完了,现在数账。一共 15 个空格,被视线照到、变绿的有 8 个,剩下没被任何视线扫到的空格有 7 个,我把它们标成蓝色。像 (0,4)、(1,1) 这些格子,四周的视线要么被墙拦下、要么根本射不到,所以谁也看不见它们。15 减 8 等于 7,这就是没被保卫的格子数。
回放 · 蓝色 7 格没人看到,答案 7：回放一遍。橙色是警卫,红色是墙,绿色是被视线照到的空格,蓝色这 7 格是没被保卫的。仔细看会发现,警卫 (0,0) 向右的视线被墙 (0,2) 挡住,所以右上角一带照不全;警卫 (2,3) 向下一步就撞上墙 (3,3),底下那格也没人管。挡板决定了视线的边界,数出蓝色格子共 7 个,答案就是它。
边界想清:警卫被墙贴身围住四角照不到、没有空格时答案 0、唯一空格被照到也答案 0。
面试重点:警卫墙记 2、逐警卫四向射线标记遇挡板停、最后数 0,时间空间都是 O(m 乘 n)。
参考代码
from __future__ import annotationsfrom 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 = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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)复杂度
- 时间：O(m·n)，开表和最后数 0 都是遍历一遍所有 m 乘 n 个格子。警卫和墙把每一行每一列切成若干空段,每个空段最多被两侧的警卫各扫一次,所以单格在水平方向和竖直方向都只被常数次经过,所有射线加起来经过的格子总数不超过格子数的常数倍,整体随格子数线性增长
- 空间：O(m·n)，按峰值算。主要开销是那张 m 乘 n 的网格表 g,用来记录每格的状态。没有额外的递归或队列,空间就是这张表本身的大小
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问为什么不用对每个空格反过来找警卫?
追问复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
道路的最大总重要性
LeetCode 2285 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题