P3515. 聚餐地点

解题思路

本题的设问是需要寻找两个人同时可以到达的聚餐地点。

一种非常朴素的做法就是按照题目的要求进行模拟：先找到两个 2 的坐标位置，然后从这两个 2 出发进行 DFS/BFS，分别记录能够到达的 3 的位置，再取交集，交集的长度就是答案。

但这种做法显得有些冗余，因为需要分别从两个起点出发进行两次搜索，并且还涉及到取交集的操作。

重新思考

由于题目中有且只有两个 2，且地图中只有 1 是障碍物。若：

• 这两个 2 不处于同一个连通块中，那么小华和小为注定无法相遇，他们能够同时到达的 3 的个数一定是 0。
• 这两个 2 处于同一个连通块中，那么小华和小为必然可以相遇，小华能够到达的 3，小为也必定可以到达，反之亦然。因此小华能够到达的 3 的个数和小为能够到达的 3 的个数是一样的，也就是他们共同能够到达的聚餐地点。

因此，我们其实不需要分别从两个 2 出发做两次搜索。只需要从其中的某一个 2 出发做一次搜索即可：

1. 设置一个标记 flag 初始化为 False，表示能够遇到另一个 2。如果搜索过程中遇到了另一个 2，那么将 flag 设置为 True。 2. 在搜索的过程中记录遇到的 3 的个数 ans。 3. 退出搜索后，若：

• flag = False，说明小华和小为无法相遇，可以同时到达的聚餐地点数量为 0。
• flag = True，说明小华和小为可以相遇，可以同时到达的聚餐地点数量为上述搜索中记录的 3 的个数 ans。

至于用 DFS 还是 BFS，那都是套模板的事情了，非常简单。

代码

解法一：DFS

复杂度分析 设网格共 n 行 m 列，格子总数为 n*m。

• 找起点 findStart：双重循环扫描网格找到某个 2 作为搜索起点，最坏 O(n*m)。
• DFS 阶段：checkList 保证每个格子至多被标记并进入递归一次；每进入一个格子只做常数量工作（检查上下左右 4 个方向的越界、访问标记与是否为障碍），所以整个搜索是 O(n*m)。
• 瓶颈就在这两处对全网格的线性扫描与一次连通块搜索上，总时间复杂度 O(n*m)。

空间复杂度 O(n*m)：grid 与 checkList 各占一个 n*m 的二维数组；此外 DFS 递归栈深度最坏情况下与连通块大小同阶，也是 O(n*m)。