欢乐的周末 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 200分

题解： 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] >> seq) & 1) == 1) {
            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 in