题目描述
思路解析动画文字版
记牢这一句:警卫和墙都是 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题