OD统一考试
题解： Java / Python / C++
题目描述
小华和小为是很要好的朋友，他们约定周末一起吃饭。
通过手机交流，他们在地图上选择了多个聚餐地点(由于自然地形等原因，部分聚餐地点不可达)。求小华和小为都能到达的聚餐地点有多少个?
输入描述
第一行输入m和n，m代表地图的长度，n代表地图的宽度
第二行开始具体输入地图信息，地图信息包含:
0 为通畅的道路
1 为障碍物 (且仅1为障碍物)
2 为小华或者小为，地图中必定有且仅有2个(非障碍物)
3 为被选中的聚餐地点 (非障碍物)
输出描述
可以被两方都到达的聚餐地点数量，行末无空格
示例1
输入：
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
示例2
输入
4 4
2 1 2 3
0 1 0 0
0 1 0 0
0 1 0 0
输出
0
题解
这是一个 **DFS（深度优先搜索）**来解决的问题，主要目标是找到两个人（小华和小为）分别从他们的起点出发，能够到达的聚餐地点的交集。
主要思路是从两个起点分别进行深度优先搜索，并用一个二维数组
vis记录访问状态。在 DFS 过程中，将访问的位置的对应位设置为1，表示这个位置被访问过。
最后，遍历所有聚餐地点，如果两个人都能到达的地点，就将结果加一。
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
private static int m, n;
private static void dfs(int[][] g, int r, int c, int[][] vis, int seq) {
if (r < 0 || c < 0 || r >= m || c >= n || g[r][c] == 1 || ((vis[r][c] & (1 << seq)) != 0)) {
return;
}
// 第 seq 个人访问(i,j) 则将 vis[i][j] 的二进制第 seq 位变为 1
vis[r][c] |= (1 << seq);
dfs(g, r + 1, c, vis, seq);
dfs(g, r - 1, c, vis, seq);
dfs(g, r, c + 1, vis, seq);
dfs(g, r, c - 1, vis, seq);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
m = scanner.nextInt();
n = scanner.nextInt();
int[][] g = new int[m][n];
int[][] vis = new int[m][n];
// 起点位置（小华或者小为的位置）
List<int[]> starts = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = scanner.nextInt();
if (g[i][j] == 2) starts.add(new int[]{i, j});
}
}
for (int i = 0; i < 2; i++) {
int[] pos = starts.get(i);
dfs(g, pos[0], pos[1], vis, i);
}
int result = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 聚餐地点 && 两次都访问到
if (g[i][j] == 3 && vis[i][j] == 3) {
result++;
}
}
}
System.out.println(result);
}
}
Python
def dfs(g, r, c, vis, seq):
if r < 0 or c < 0 or r >= m or c >= n or g[r][c] == 1 or (vis[r][c] & (1 << seq)) != 0:
return
# 第 seq 个人访问(i,j) 则将 vis[i][j] 的二进制第 seq 位变为 1
vis[r][c] |= (1 << seq)
dfs(g, r + 1, c, vis, seq)
dfs(g, r - 1, c, vis, seq)
dfs(g, r, c + 1, vis, seq)
dfs(g, r, c - 1, vis, seq)
m, n = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(m)]
vis = [[0] * n for _ in range(m)]
# 起点位置（小华或者小为的位置）
starts = [(r, c) for r in range(m) for c in range(n) if g[r][c] == 2]
for seq, (r, c) in enumerate(starts):
dfs(g, r, c, vis, seq)
result = sum(1 for r in range(m) for c in range(n) if g[r][c] == 3 and vis[r][c] == 3)
print(result)
C++
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int m, n;
void dfs(vector<vector<int>>& g, int r, int c, vector<vector<int>>& vis, int seq) {
if(r < 0 || c < 0 || r >= m || c >= n || g[r][c] == 1 || (vis[r][c] & (1 << seq))) return;
vis[r][c] |= (1 << seq);
dfs(g, r + 1, c, vis, seq);
dfs(g, r - c, c, vis, seq);
dfs(g, r, c + 1, vis, seq);
dfs(g, r, c - 1, vis, seq);
}
int main() {
cin >> m >> n;
vector<pair<int, int>> starts; // 起点位置（小华或者小为的位置）
vector<vector<int>> g(m, vector<int>(n, 0));
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
cin >> g[i][j];
if(g[i][j] == 2) {
starts.push_back({i, j});
}
}
}
// vis[i][j] 表示访问状态, 第 seq 个人访问(i,j) 则将 vis[i][j] 的二进制第 seq 位变为 1
vector<vector<int>> vis(m, vector<int>(n, 0));
for(int i=0; i < 2; i++) {
dfs(g, starts[i].first, starts[i].second, vis, i);
}
int result = 0;
for(int i=0; i<m; i++) {
for(int j= 0; j<n; j++) {
// 聚餐地点 && 两次都访问到
if(g[i][j] == 3 && vis[i][j] == 3) {
result ++;
}
}
}
cout << result << endl;
return 0;
}
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
