一、题目
小华和小为是很要好的朋友，他们约定周末一起吃饭
通过手机交流，他们在地图上选择了多个聚餐地点
(由于自然地形等原因，部分聚餐地点不可达)
求小华和小为都能到达的聚餐地点有多少个?
二、输入
第一行输入m和n，m代表地图的长度，
n代表地图的宽度第二行开始具体输入地图信息，
地图信息包含:
0 为通畅的道路
1 为障碍物 (且仅1为障碍物)
2 为小华或者小为，地图中必定有且仅有2个(非障碍物)
3 为被选中的聚餐地点 (非障碍物)
三、输出
可以被两方都到达的聚餐地点数量，行未无空格
四、示例
示例一
输入：
4 4
2 1 0 3
0 1 2 1
0 3 0 0
0 0 0 0
输出：
2
- 说明：第一行输入地图的长宽为4，4， 接下来4行是地图2表示华为的位置， 3是聚餐地点，图中的两个3， 小华和小为都可到达，所以输出2
示例二
输入：
4 4
2 1 2 3
0 1 0 0
0 1 0 0
0 1 0 0
输出：
0
五、题解
- 本题本质上是图的遍历问题（BFS 或者 DFS）。注意避免重复遍历需要记录已经访问过的点。两轮遍历每次都重置访问数组
- 注意输入数据的读取、队列、集合操作的 API 等基本功
5.1 Java 实现
package org.stone.study.algo.ex202411;
import java.util.*;
/**
* 小华和小为是很要好的朋友，他们约定周末一起吃饭
*
* 通过手机交流，他们在地图上选择了多个聚餐地点
* (由于自然地形等原因，部分聚餐地点不可达)
* 求小华和小为都能到达的聚餐地点有多少个?
*
* 第一行输入m和n，m代表地图的长度，
* n代表地图的宽度第二行开始具体输入地图信息，
* 地图信息包含:
* 0 为通畅的道路
* 1 为障碍物 (且仅1为障碍物)
* 2 为小华或者小为，地图中必定有且仅有2个(非障碍物)
* 3 为被选中的聚餐地点 (非障碍物)
*/
public class ReachableRestauran {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
// 显式读取行尾的换行符
scanner.nextLine();
int[][] grid = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = scanner.nextInt();
}
// 显式读取行尾的换行符
scanner.nextLine();
}
int ans = reachableRestaurant(m, n, grid);
System.out.println(ans);
}
private static int reachableRestaurant(int m, int n, int[][] grid) {
// 记录小华和小为的位置，刚好 2 个
int[][] starts = new int[2][2];
int k = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 2) {
starts[k][0] = i;
starts[k][1] = j;
++k;
}
}
}
Set<Long> set1 = bfs(grid, starts[0][0], starts[0][1]);
Set<Long> set2 = bfs(grid, starts[1][0], starts[1][1]);
// 求交集，结果放在 set1 中
set1.retainAll(set2);
return set1.size();
}
/**
* 从(x, y)开始 BFS 遍历，返回所有能到达的 3 的位置的集合
* @param grid
* @param x
* @param y
* @return
*/
private static Set<Long> bfs(int[][] grid, int x, int y) {
// 存放所有能到达的 3 的位置的集合
Set<Long> res = new HashSet<>();
int m = grid.length;
int n = grid[0].length;
// 标记已经访问过的位置
boolean[][] visited = new boolean[m][n];
for(int i = 0; i < m; i++) {
Arrays.fill(visited[i], false);
}
// 方向数组
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// BFS 队列
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
visited[x][y] = true;
while(!queue.isEmpty()) {
int[] cur = queue.poll();
int i = cur[0];
int j = cur[1];
// 能走到一家餐厅，加入结果集
if(grid[i][j] == 3) {
// 二维坐标转一维坐标，原因是 Set 中不建议放数组，转换为不变量Long
res.add((long)i * n + j);
}
for(int[] dir : dirs) {
int nextX = i + dir[0];
int nextY = j + dir[1];
if(nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY]
&& grid[nextX][nextY] != 1) {
queue.offer(new int[]{nextX, nextY});
visited[nextX][nextY] = true;
}
}
}
return res;
}
}5.2 Python实现
def calcCommonRestaurants(grid):
m, n = len(grid), len(grid[0])
# 找小华和小为的起点
startPoints = []
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
startPoints.append((i, j))
restSet1 = dfs(grid, startPoints[0][0], startPoints[0][1])
restSet2 = dfs(grid, startPoints[1][0], startPoints[1][1])
# 找共同的餐厅
commonRestaurants = restSet1.intersection(restSet2)
return len(commonRestaurants)
def dfs(grid, i, j):
m, n = len(grid), len(grid[0])
# 存放访问过的位置，避免重复访问
visited = set()
visited.add((i, j))
restaurants = set()
# 存放访问过的位置，遍历过程中出队
queue = [(i, j)]
# 定义四个方向的移动
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
x, y = queue.pop()
if grid[x][y] == 3:
restaurants.add((x, y))
for dx, dy in directions:
new_x, new_y = x + dx, y + dy
# 检查新位置是否有效且未访问过
if (0 <= new_x < m and 0 <= new_y < n and
grid[new_x][new_y] != 1 and
(new_x, new_y) not in visited):
visited.add((new_x, new_y))
queue.append((new_x, new_y))
return restaurants
if __name__ == '__main__':
m, n = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(m)]
commonRestaurants = calcCommonRestaurants(grid)
print(commonRestaurants)