返回目录

题目描述

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

输入描述

第一行输入m和n，m代表地图的长度，n代表地图的宽度。

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

0 为通畅的道路

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

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

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

输出描述

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

示例：

Python算法源码

# 定义四个方向的偏移量（上、下、左、右）
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]

# 深度优先搜索函数
def dfs(currX, currY, targetX, targetY, m, n, map, visited, person):
    # 如果当前位置就是目标位置，返回True
    if currX == targetX and currY == targetY:
        return True

    # 遍历四个方向
    for dx, dy in dirs:
        nextX, nextY = currX + dx, currY + dy
        # 如果下一个位置超出地图范围，或者是障碍物，或者已经访问过，跳过
        if nextX < 0 or nextY < 0 or nextX >= m or nextY >= n or map[nextX][nextY] == 1 or visited[nextX][nextY]:
            continue

        # 标记下一个位置为已访问
        visited[nextX][nextY] = True
        # 递归搜索下一个位置
        if dfs(nextX, nextY, targetX, targetY, m, n, map, visited, person):
            return True

    return False

def main():
    m, n = map(int, input().split()) # 读取地图的长和宽
    map_info = [] # 地图列表
    visited = [[False] * n for _ in range(m)] # 访问标记列表
    persons = [] # 人物位置列表
    targets = [] # 目标位置列表

    # 读取地图信息，并记录小华和小为的位置以及聚餐地点
    for i in range(m):
        row = list(map(int, input().split()))
        map_info.append(row)
        for j, val in enumerate(row):
            if val == 2:
                persons.append((i, j))
            elif val == 3:
                targets.append((i, j))

    res = 0 # 可以被两人都到达的聚餐地点数量

    # 遍历所有聚餐地点
    for target in targets:
        can_reach = True # 标记是否都可以到达
        for person in range(2): # 对于小华和小为
            # 重置visited列表
            visited = [[False] * n for _ in range(m)]
            # 判断是否能到达目标位置
            if not dfs(persons[person][0], persons[person][1], target[0], target[1], m, n, map_info, visited, person):
                can_reach = False
                break
        if can_reach:
            res += 1

    print(res) # 输出结果

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>

// 定义四个方向的偏移量（上、下、左、右）
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

// 深度优先搜索函数
int dfs(int currX, int currY, int targetX, int targetY, int **map, int ***visited, int person, int m, int n) {
    // 如果当前位置就是目标位置，返回1
    if (currX == targetX && currY == targetY) {
        return 1;
    }

    // 遍历四个方向
    for (int i = 0; i < 4; ++i) {
        int nextX = currX + dirs[i][0], nextY = currY + dirs[i][1];
        // 如果下一个位置超出地图范围，或者是障碍物，或者已经访问过，跳过
        if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n || map[nextX][nextY] == 1 || visited[nextX][nextY][person]) {
            continue;
        }

        // 标记下一个位置为已访问
        visited[nextX][nextY][person] = 1;
        // 递归搜索下一个位置
        if (dfs(nextX, nextY, targetX, targetY, map, visited, person, m, n)) {
            return 1;
        }
    }

    return 0;
}

int main() {
    // 输入初始化
    int m, n;
    scanf("%d %d", &m, &n);
    int **map = (int **)malloc(m * sizeof(int *));
    int ***visited = (int ***)malloc(m * sizeof(int **));
    for (int i = 0; i < m; ++i) {
        map[i] = (int *)malloc(n * sizeof(int));
        visited[i] = (int **)malloc(n * sizeof(int *));
        for (int j = 0; j < n; ++j) {
            visited[i][j] = (int *)malloc(2 * sizeof(int));
        }
    }
    int persons[2][2] = {{-1, -1}, {-1, -1}};
    int targets_count = 0;

    // 读取地图信息，并记录小华和小为的位置以及聚餐地点
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 2) {
                if (persons[0][0] == -1) {
                    persons[0][0] = i;
                    persons[0][1] = j;
                } else {
                    persons[1][0] = i;
                    persons[1][1] = j;
                }
            } else if (map[i][j] == 3) {
                targets_count++;
            }
        }
    }

    // 获取小华和小为的位置
    int xiaohua[2] = {persons[0][0], persons[0][1]};
    int xiaowei[2] = {persons[1][0], persons[1][1]};
    int res = 0;

    // 遍历所有聚餐地点
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (map[i][j] == 3) {
                // 重置visited数组
                for (int k = 0; k < m; ++k) {
                    for (int l = 0; l < n; ++l) {
                        for (int p = 0; p < 2; ++p) {
                            visited[k][l][p] = 0;
                        }
                    }
                }
                // 判断小华是否能到达目标位置
                if (dfs(xiaohua[0], xiaohua[1], i, j, map, visited, 0, m, n)) {
                    // 重置visited数组
                    for (int k = 0; k < m; ++k) {
                        for (int l = 0; l < n; ++l) {
                            for (int p = 0; p < 2; ++p) {
                                visited[k][l][p] = 0;
                            }
                        }
                    }
                    // 判断小为是否能到达目标位置
                    if (dfs(xiaowei[0], xiaowei[1], i, j, map, visited, 1, m, n)) {
                        // 如果两个人都能到达目标位置，结果加1
                        res++;
                    }
                }
            }
        }
    }

    // 输出可以被两人都到达的聚餐地点数量
    printf("%d\n", res);

    // 释放内存
    for (int i = 0; i < m; ++i) {
        free(map[i]);
        for (int j = 0; j < n; ++j) {
            free(visited[i][j]);
        }
        free(visited[i]);
    }
    free(map);
    free(visited);

    return 0;
}

Java算法源码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    // 定义四个方向的偏移量（上、下、左、右）
    static final int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    // 深度优先搜索函数
    static boolean dfs(int currX, int currY, int targetX, int targetY, int[][] map, boolean[][][] visited, int person) {
        // 如果当前位置就是目标位置，返回true
        if (currX == targetX && currY == targetY) {
            return true;
        }

        // 遍历四个方向
        for (int[] dir : dirs) {
            int nextX = currX + dir[0], nextY = currY + dir[1];
            // 如果下一个位置超出地图范围，或者是障碍物，或者已经访问过，跳过
            if (nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length || map[nextX][nextY] == 1 || visited[nextX][nextY][person]) {
                continue;
            }

            // 标记下一个位置为已访问
            visited[nextX][nextY][person] = true;
            // 递归搜索下一个位置
            if (dfs(nextX, nextY, targetX, targetY, map, visited, person)) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        // 输入初始化
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] map = new int[m][n];
        // 使用三维数组visited来记录每个人访问过的位置
        boolean[][][] visited = new boolean[m][n][2];
        List<int[]> persons = new ArrayList<>();
        List<int[]> targets = new ArrayList<>();

        // 读取地图信息，并记录小华和小为的位置以及聚餐地点
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                map[i][j] = scanner.nextInt();
                if (map[i][j] == 2) {
                    persons.add(new int[]{i, j});
                } else if (map[i][j] == 3) {
                    targets.add(new int[]{i, j});
                }
            }
        }

        // 获取小华和小为的位置
        int[] xiaohua = persons.get(0);
        int[] xiaowei = persons.get(1);
        int res = 0;

        // 遍历所有聚餐地点
        for (int[] target : targets) {
            // 重置visited数组
            visited = new boolean[m][n][2];
            // 判断小华是否能到达目标位置
            if (dfs(xiaohua[0], xiaohua[1], target[0], target[1], map, visited, 0)) {
                // 重置visited数组
                visited = new boolean[m][n][2];
                // 判断小为是否能到达目标位置
                if (dfs(xiaowei[0], xiaowei[1], target[0], target[1], map, visited, 1)) {
                    // 如果两个人都能到达目标位置，结果加1
                    res++;
                }
            }
        }

        // 输出可以被两人都到达的聚餐地点数量
        System.out.println(res);
    }
}