P3506. 陷阱方格

解题思路

本题是一道非常有意思的题目，显然路径的搜索过程可以用 DFS/BFS 来完成。问题在于如何判断方格是不可达方格和陷阱方格。

不可达方格的判断

先考虑相对直观的不可达方格的判断。 我们从起点到终点进行 DFS/BFS（注意搜索方向只有向上或向右两个方向），将能够到达的方格在检查数组 check_list1 中标记为 True。搜索完成后，check_list1 中所有不为墙壁的 False 数量，即为不可达方格的数量。

显然上述做法只能够算出不可达方格的数量，因为陷阱方格在搜索过程中是可以到达的。

逆向路径的概念

在判断陷阱方格之前，需要构建一个逆向路径的概念。 如果从某个点 (i, j) 出发（这个点不一定是起点），只历经向右和向上最终到达终点，那么相对应的，从终点出发也可以只历经向左和向下最终到达该点 (i, j)，这条路径我们称之为原路径的逆向路径。

容易证明，如果某条路径存在，那么其逆向路径也一定存在。

陷阱方格的判断

陷阱方格的判断需要借助逆向路径的概念来完成。假设一个方格 (i, j) 是陷阱方格，它应该满足以下两个要求：

1. 从起点出发，能够到达 (i, j)。即从 (0, 0) 到 (i, j) 的路径存在。 2. 从 (i, j) 出发，不能够到达终点 (n-1, m-1)。即从 (i, j) 出发到终点 (n-1, m-1) 的路径不存在。

上述第一个条件其实非常容易满足。在不可达方格判断中，check_list1 中标记为 True 的点，就是从起点出发能够到达的点。

对于上述的第二个条件，我们可以用逆向路径的概念来描述： 从终点 (n-1, m-1) 出发到点 (i, j) 的逆向路径不存在。

因此对于第二个条件，我们可以从终点到起点进行逆向路径的 DFS/BFS（注意搜索方向只有向左或向下两个方向），能够到达的位置在检查数组 check_list2 中标记为 True。搜索完成后，check_list2 中所有不为墙壁的值为 False 的点，即为从终点出发的逆向路径无法到达的点。

在 check_list1 中值为 True，在 check_list2 中值为 False 的点（且不为墙壁），即是满足上述两个条件的点，也就是陷阱方格。统计满足条件的方格数量即可。

其他特殊处理

至此，本题的分析已经大体完成，我们需要做两次 DFS/BFS 搜索：

• 第一次从起点出发往终点搜寻，方向只有向上和向右
• 第二次从终点出发往起点搜寻，方向只有向下和向左

不管是 BFS 过程还是 DFS 过程，和常规的搜索过程无异。

另外，考虑到在计算 checkList 中值的时候需要排除掉墙壁，我们可以在墙壁的初始化时，就把 checkList1 和 checkList2 中墙壁所对应的点标记为 True，这样可以免去最后一步计数时的繁琐判断。

代码

解法一：BFS

复杂度分析 设房间为 n 行 m 列（对应题面的 X * Y），墙壁数量为 W。

• 时间：算法共做两次 BFS。第一次从起点 (0, 0) 出发只向右、向上扩展，第二次从终点 (n-1, m-1) 出发只向左、向下扩展。两次 BFS 中每个格子分别由 checkList1、checkList2 保证最多入队一次，每次出队只检查 2 个方向，所以各是 O(n·m)。之后统计不可达方格与陷阱方格又各做一次全网格双重循环 O(n·m)，读入墙壁是 O(W)。由于 W ≤ n·m，总时间复杂度为 O(n·m)。
• 空间：grid、checkList1、checkList2 三个二维数组各占 O(n·m)，队列最坏情况下同量级，空间复杂度为 O(n·m)。

另外，代码在读入墙壁时就把两个 checkList 中墙壁对应的位置预先标为 true，这个小技巧既挡住了 BFS 进入墙壁，也让最后两轮计数不必再单独排除墙壁，且不增加复杂度。