华为OD 机试 - 聚餐地点（Java & Python & C++）

五分钟学算法

发布于 2024-04-14 09:04:12

1130

发布于 2024-04-14 09:04:12

文章被收录于专栏：五分钟学算法五分钟学算法

本题练习地址：https://oj.algomooc.com/

一、题目描述与示例

题目描述

小华和小为是很好的朋友，他们约定周末一起吃饭，通过手机交流，他们在地图上选择了很多聚餐地点（由于自然地形等原因，部分聚餐地点不可达），求小华和小为都能达到的聚餐地点有多少个。

输入描述

第一行输入 m 和 n，m 表示地图长度，n 表示地图宽度

第二行开始具体输入地图信息，地图信息包括

0 为通畅的道路

1 为障碍物（且仅 1 为障碍物）

2 为小华或小为，地图中必定有且仅有两个（非障碍物）

3 为被选中的聚餐地点（非障碍物）

输出描述

可以两方都到达的聚餐地点的数量，行末无空格

补充说明

地图长宽为m和n,4 <= m <= 100 ，4 <= n <= 100

聚餐的地点数量为k，则1 < k <= 100

示例

输入

输出

备注

第一行输入地图的长宽为4和4

第二行开始为具体的地图，其中：

3 代表小华和小明的聚餐地点；

2 代表小华或小明（确保有2个）；

0 代表可以通行的位置；

1 代表不可以出行的位置。

此时2者都能达到的聚餐位置有两处

二、解题思路

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

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

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

重新思考这个问题：由于题目中有且只有两个2，且地图中只有1是障碍物。若

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

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

设置一个标记flag初始化为False，表示能够遇到另一个2。如果搜索过程中遇到了另一个2，那么将flag设置为True
在搜索的过程中记录遇到的3的个数ans。
退出搜索后，若
- flag = False，说明小华和小为无法相遇，可以同时到达的聚餐地点数量为0
- flag = True，说明小华和小为可以相遇，可以同时到达的聚餐地点数量为上述搜索中记录的3的个数ans

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

三、代码

解法一：DFS

Python

# 题目：【DFS&BFS】2023C-聚餐地点
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问

import sys
sys.setrecursionlimit(10000)

# 初始化上下左右四个方向的数组
DERICTIONS = [(0,1), (1,0), (0,-1), (-1,0)]


# 用于找到起始点（某一个2）的函数
def find_start(grid, n, m):
    # 对整个grid二维数组进行双重循环遍历，
    for i in range(n):
        for j in range(m):
            # 找到其中的一个2之后，返回
            if grid[i][j] == 2:
                return i, j

# 构建DFS函数
def DFS(grid, i, j, checkList):
    global flag, ans
    # 将该点标记为已经检查过
    checkList[i][j] = True    
    # 遍历上下左右四个方向的邻点坐标
    for dx, dy in DERICTIONS:
        next_i, next_j = i + dx, j + dy
        # 若近邻点满足三个条件：
        # 1.没有越界    2. 近邻点尚未被检查过   3.近邻点不为障碍
        if ((0 <= next_i < n and 0 <= next_j < m) and checkList[next_i][next_j] == False
            and grid[next_i][next_j] != 1):
            # 如果存在近邻点是2，表示两个2互相联通，设置flag为True
            if grid[next_i][next_j] == 2:
                flag = True
            # 如果存在近邻点是3，则说明聚餐地点+1，ans += 1
            if grid[next_i][next_j] == 3:
                ans += 1
            # 对近邻点(ni, nj)进行DFS搜索
            DFS(grid, next_i, next_j, checkList)


# 输入地图的行数，列数
n, m = map(int, input().split())
# 构建网格
grid = list()
for _ in range(n):
    grid.append(list(map(int, input().split())))

# 初始化答案变量ans为0，表示能够同时到达的聚餐地点，
ans = 0

# 初始化标记flag为False，表示两个2是否相互联通
flag = False

# 调用find_start，找到搜索起点
si, sj = find_start(grid, n, m)

# 初始化数组checkList用于DFS遍历过程中的检查
# 0表示尚未访问，1表示已经访问
checkList = [[False] * m for _ in range(n)]

# 调用DFS函数，传入起点
DFS(grid, si, sj, checkList)

# 输出答案，若最后flag为True，则输出ans，否则输出0
print(ans) if flag else print(0)

Java

import java.util.*;

public class Main {
    // 上下左右四个方向的数组
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    // 用于找到起始点（某一个2）的函数
    private static int[] findStart(int[][] grid, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1}; // 没有找到起始点
    }

    // 构建DFS函数
    private static void DFS(int[][] grid, int i, int j, boolean[][] checkList, boolean[] flag, int[] ans) {
        int n = grid.length;
        int m = grid[0].length;

        // 将该点标记为已经检查过
        checkList[i][j] = true;

        // 遍历上下左右四个方向的邻点坐标
        for (int[] dir : DIRECTIONS) {
            int next_i = i + dir[0];
            int next_j = j + dir[1];

            // 若近邻点满足三个条件：
            // 1.没有越界    2. 近邻点尚未被检查过   3.近邻点也为陆地
            if (next_i >= 0 && next_i < n && next_j >= 0 && next_j < m
                    && !checkList[next_i][next_j] && grid[next_i][next_j] != 1) {
                // 如果存在近邻点是2，表示两个2互相联通，设置flag为True
                if (grid[next_i][next_j] == 2) {
                    flag[0] = true;
                }
                // 如果存在近邻点是3，则说明聚餐地点+1，ans[0] += 1
                if (grid[next_i][next_j] == 3) {
                    ans[0]++;
                }
                // 对近邻点(next_i, next_j)进行DFS搜索
                DFS(grid, next_i, next_j, checkList, flag, ans);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入行数，列数
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine(); // 读取换行符

        // 构建网格
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        // 初始化答案变量ans为0，表示能够同时到达的聚餐地点
        int[] ans = {0};

        // 初始化标记flag为False，表示两个2是否相互联通
        boolean[] flag = {false};

        // 调用findStart，找到搜索起点
        int[] start = findStart(grid, n, m);

        // 初始化数组checkList用于DFS遍历过程中的检查
        // false表示尚未访问，true表示已经访问
        boolean[][] checkList = new boolean[n][m];

        // 调用DFS函数，传入起点
        DFS(grid, start[0], start[1], checkList, flag, ans);

        // 输出答案，若最后flag为True，则输出ans[0]，否则输出0
        System.out.println(flag[0] ? ans[0] : 0);
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

// 上下左右四个方向的数组
vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

// 用于找到起始点（某一个2）的函数
pair<int, int> findStart(vector<vector<int>>& grid, int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 2) {
                return {i, j};
            }
        }
    }
    return {-1, -1}; // 没有找到起始点
}

// 构建DFS函数
void DFS(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& checkList, bool& flag, int& ans) {
    int n = grid.size();
    int m = grid[0].size();

    // 将该点标记为已经检查过
    checkList[i][j] = true;

    // 遍历上下左右四个方向的邻点坐标
    for (auto& dir : DIRECTIONS) {
        int next_i = i + dir.first;
        int next_j = j + dir.second;

        // 若近邻点满足三个条件：
        // 1.没有越界    2. 近邻点尚未被检查过   3.近邻点也为陆地
        if (next_i >= 0 && next_i < n && next_j >= 0 && next_j < m
                && !checkList[next_i][next_j] && grid[next_i][next_j] != 1) {
            // 如果存在近邻点是2，表示两个2互相联通，设置flag为True
            if (grid[next_i][next_j] == 2) {
                flag = true;
            }
            // 如果存在近邻点是3，则说明聚餐地点+1，ans += 1
            if (grid[next_i][next_j] == 3) {
                ans++;
            }
            // 对近邻点(next_i, next_j)进行DFS搜索
            DFS(grid, next_i, next_j, checkList, flag, ans);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    // 构建网格
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    // 初始化答案变量ans为0，表示能够同时到达的聚餐地点
    int ans = 0;

    // 初始化标记flag为False，表示两个2是否相互联通
    bool flag = false;

    // 调用findStart，找到搜索起点
    auto [si, sj] = findStart(grid, n, m);

    // 初始化数组checkList用于DFS遍历过程中的检查
    // false表示尚未访问，true表示已经访问
    vector<vector<bool>> checkList(n, vector<bool>(m, false));

    // 调用DFS函数，传入起点
    DFS(grid, si, sj, checkList, flag, ans);

    // 输出答案，若最后flag为True，则输出ans，否则输出0
    cout << (flag ? ans : 0) << endl;

    return 0;
}

时空复杂度

时间复杂度：O(NM)。

空间复杂度：O(NM)。

解法二：BFS

Python

# 题目：【DFS&BFS】2023C-聚餐地点
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问


from collections import deque

# 初始化上下左右四个方向的数组
DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]

# 用于找到起始点（某一个2）的函数
def find_start(grid, n, m):
    # 对整个grid二维数组进行双重循环遍历，
    for i in range(n):
        for j in range(m):
            # 找到其中的一个2之后，返回
            if grid[i][j] == 2:
                return i, j


# 输入地图的行数，列数
n, m = map(int, input().split())
# 构建网格
grid = list()
for _ in range(n):
    grid.append(list(map(int, input().split())))

# 初始化答案变量ans为0，表示能够同时到达的聚餐地点，
ans = 0

# 初始化标记flag为False，表示两个2是否相互联通
flag = False

# 调用find_start，找到搜索起点
si, sj = find_start(grid, n, m)

# 初始化数组checkList用于DFS遍历过程中的检查
# 0表示尚未访问，1表示已经访问
checkList = [[False] * m for _ in range(n)]

# 初始化队列
q = deque()
q.append((si, sj))
# 修改checkList[si][sj]为1，表示起始位置已经搜寻过
checkList[si][sj] = 1

# 进行BFS，退出循环的条件是队列为空
while len(q) > 0:
    # 弹出栈队头的点(x,y) 搜寻该点上下左右的近邻点
    x, y = q.popleft()
    # 遍历(x,y)上下左右的四个方向的近邻点
    for dx, dy in DIRECTIONS:
        x_next, y_next = x+dx, y+dy
        # 如果近邻点满足三个条件
        if (0 <= x_next < n and 0 <= y_next < m and checkList[x_next][y_next] == 0
            and grid[x_next][y_next] != 1):
            # 对近邻点做两件事：
            # 1. 入队       2. 标记为已检查过    3. 查看是否是2或3
            q.append((x_next, y_next))
            checkList[x_next][y_next] = 1
            # 如果存在近邻点是2，表示两个2互相联通，设置flag为True
            if grid[x_next][y_next] == 2:
                flag = True
            # 如果存在近邻点是3，则说明聚餐地点+1，ans += 1
            if grid[x_next][y_next] == 3:
                ans += 1

# 输出答案，若最后flag为True，则输出ans，否则输出0
print(ans) if flag else 0

Java

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    // 上下左右四个方向的数组
    static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    // 用于找到起始点（某一个2）的函数
    static int[] findStart(int[][] grid, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1}; // 没有找到起始点
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        int ans = 0;
        boolean flag = false;
        int[] start = findStart(grid, n, m);

        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(start);

        boolean[][] checkList = new boolean[n][m];
        checkList[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            for (int[] dir : DIRECTIONS) {
                int x_next = x + dir[0];
                int y_next = y + dir[1];

                if (x_next >= 0 && x_next < n && y_next >= 0 && y_next < m
                        && !checkList[x_next][y_next] && grid[x_next][y_next] != 1) {
                    queue.add(new int[]{x_next, y_next});
                    checkList[x_next][y_next] = true;

                    if (grid[x_next][y_next] == 2) {
                        flag = true;
                    }
                    if (grid[x_next][y_next] == 3) {
                        ans++;
                    }
                }
            }
        }

        System.out.println(flag ? ans : 0);
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 上下左右四个方向的数组
const vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

// 用于找到起始点（某一个2）的函数
pair<int, int> findStart(vector<vector<int>>& grid, int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 2) {
                return make_pair(i, j);
            }
        }
    }
    return make_pair(-1, -1); // 没有找到起始点
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    int ans = 0;
    bool flag = false;
    pair<int, int> start = findStart(grid, n, m);

    queue<pair<int, int>> q;
    q.push(start);

    vector<vector<bool>> checkList(n, vector<bool>(m, false));
    checkList[start.first][start.second] = true;

    while (!q.empty()) {
        pair<int, int> current = q.front();
        q.pop();
        int x = current.first;
        int y = current.second;

        for (const auto& dir : DIRECTIONS) {
            int x_next = x + dir.first;
            int y_next = y + dir.second;

            if (x_next >= 0 && x_next < n && y_next >= 0 && y_next < m
                    && !checkList[x_next][y_next] && grid[x_next][y_next] != 1) {
                q.push(make_pair(x_next, y_next));
                checkList[x_next][y_next] = true;

                if (grid[x_next][y_next] == 2) {
                    flag = true;
                }
                if (grid[x_next][y_next] == 3) {
                    ans++;
                }
            }
        }
    }

    cout << (flag ? ans : 0) << endl;

    return 0;
}