【华为OD机试】欢乐的周末（C++ Java JavaScript Python）

原文链接

【华为OD机试】欢乐的周末（C++ Java JavaScript Python）

题目描述

小华和小为是很要好的朋友，他们约定周末一起吃饭。

通过手机交流，他们在地图上选择了多个聚餐地点（由于自然地形等原因，部分聚餐地点不可达），求小华和小为都能到达的聚餐地点有多少个？

输入描述

第一行输入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

输出

说明

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

第二行开始为具体的地图，其中：3代表小华和小明选择的聚餐地点；2代表小华或者小明（确保有2个）；0代表可以通行的位置；1代表不可以通行的位置。

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

输入

4 4
2 1 2 3
0 1 0 0
0 1 0 0
0 1 0 0

输出

说明

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

由于图中小华和小为之间有个阻隔，此时，没有两人都能到达的聚餐地址，故而返回0。

备注：

地图的长宽为m和n，其中：

4 <= m <= 100

4 <= n <= 100

聚餐的地点数量为 k，则

1< k <= 100

C++

#include <iostream>
#include <vector>
using namespace std;

// 并查集实现
class UnionFindSet {
private:
    vector<int> fa;

public:
    UnionFindSet(int n) {
        fa.resize(n);
        for (int i = 0; i < n; i++) fa[i] = i;
    }

    int find(int x) {
        if (x != fa[x]) {
            fa[x] = find(fa[x]);
            return fa[x];
        }
        return x;
    }

    void merge(int x, int y) {
        int x_fa = find(x);
        int y_fa = find(y);

        if (x_fa != y_fa) {
            fa[y_fa] = x_fa;
        }
    }
};

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> matrix(n, vector<int>(m, 0));

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

    UnionFindSet ufs(n * m);

    vector<int> huawei; // 记录小华位置
    vector<int> restaurants; // 记录聚餐地点位置

    vector<vector<int>> offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 偏移量

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] != 1) { // 如果是障碍物则不处理
                int x = i * m + j; // 将二维坐标转换为一维坐标
                if (matrix[i][j] == 2) huawei.push_back(x); // 记录小华位置
                else if (matrix[i][j] == 3) restaurants.push_back(x); // 记录聚餐地点位置

                for (auto offset : offsets) { // 遍历四个方向
                    int newI = i + offset[0];
                    int newJ = j + offset[1];
                    if (newI >= 0 && newI < n && newJ >= 0 && newJ < m && matrix[newI][newJ] != 1) {
                        ufs.merge(x, newI * m + newJ); // 合并连通块
                    }
                }
            }
        }
    }

    int hua_fa = ufs.find(huawei[0]); // 获取小华所在连通块的祖先
    int wei_fa = ufs.find(huawei[1]); // 获取小为所在连通块的祖先

    if (hua_fa != wei_fa) { // 如果小华和小为不在同一个连通块中，说明没有共同到达的聚餐地点
        cout << 0 << endl;
        return 0;
    }

    int ans = 0;
    for (auto restaurant : restaurants) { // 遍历所有聚餐地点
        if (ufs.find(restaurant) == hua_fa) { // 如果聚餐地点和小华在同一个连通块中
            ans++; // 答案加一
        }
    }

    cout << ans << endl; // 输出答案

    return 0;
}

JavaScript

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n, m;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    [m, n] = lines[0].split(" ").map(Number);
  }

  if (n && lines.length === n + 1) {
    lines.shift();
    const grid = lines.map((line) => line.split(" ").map(Number));

    const n = grid.length;
    const m = grid[0].length;

    const ufs = new UnionFindSet(n * m);

    const huawei = [];
    const restrant = [];
    const offsets = [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ];

    for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {
        if (grid[i][j] !== 1) {
          const x = i * m + j;
          if (grid[i][j] === 2) huawei.push(x);
          else if (grid[i][j] === 3) restrant.push(x);

          for (let offset of offsets) {
            const newI = i + offset[0];
            const newJ = j + offset[1];
            if (
              newI >= 0 &&
              newI < n &&
              newJ >= 0 &&
              newJ < m &&
              grid[newI][newJ] != 1
            ) {
              ufs.union(x, newI * m + newJ);
            }
          }
        }
      }
    }

    const [hua, wei] = huawei;
    const hua_fa = ufs.find(hua);
    const wei_fa = ufs.find(wei);
    if (hua_fa !== wei_fa) {
      console.log(0);
    } else {
      console.log(restrant.filter((r) => ufs.find(r) === hua_fa).length);
    }

    lines.length = 0;
  }
});

class UnionFindSet {
  constructor(n) {
    this.fa = new Array(n).fill(0).map((_, idx) => idx);
  }

  find(x) {
    if (x !== this.fa[x]) {
      return (this.fa[x] = this.find(this.fa[x]));
    }
    return x;
  }

  union(x, y) {
    const x_fa = this.find(x);
    const y_fa = this.find(y);

    if (x_fa !== y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

Java

import java.util.*;

class Main {
    // 并查集实现
    static class UnionFindSet {
    private int[] fa;

    public UnionFindSet(int n) {
        fa = new int[n];
        for (int i = 0; i < n; i++) fa[i] = i;
    }

    public int find(int x) {
        if (x != fa[x]) {
            fa[x] = find(fa[x]);
            return fa[x];
        }
        return x;
    }

    public void merge(int x, int y) {
        int x_fa = find(x);
        int y_fa = find(y);

        if (x_fa != y_fa) {
            fa[y_fa] = x_fa;
        }
    }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] matrix = new int[n][m];

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

        UnionFindSet ufs = new UnionFindSet(n * m);

        List<Integer> huawei = new ArrayList<>(); // 记录小华位置
        List<Integer> restaurants = new ArrayList<>(); // 记录聚餐地点位置

        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 偏移量

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] != 1) { // 如果是障碍物则不处理
                    int x = i * m + j; // 将二维坐标转换为一维坐标
                    if (matrix[i][j] == 2) huawei.add(x); // 记录小华位置
                    else if (matrix[i][j] == 3) restaurants.add(x); // 记录聚餐地点位置

                    for (int[] offset : offsets) { // 遍历四个方向
                        int newI = i + offset[0];
                        int newJ = j + offset[1];
                        if (newI >= 0 && newI < n && newJ >= 0 && newJ < m && matrix[newI][newJ] != 1) {
                            ufs.merge(x, newI * m + newJ); // 合并连通块
                        }
                    }
                }
            }
        }

        int hua_fa = ufs.find(huawei.get(0)); // 获取小华所在连通块的祖先
        int wei_fa = ufs.find(huawei.get(1)); // 获取小为所在连通块的祖先

        if (hua_fa != wei_fa) { // 如果小华和小为不在同一个连通块中，说明没有共同到达的聚餐地点
            System.out.println(0);
            return;
        }

        int ans = 0;
        for (int restaurant : restaurants) { // 遍历所有聚餐地点
            if (ufs.find(restaurant) == hua_fa) { // 如果聚餐地点和小华在同一个连通块中
                ans++; // 答案加一
            }
        }

        System.out.println(ans); // 输出答案
    }
}

Python

class UnionFindSet:
    def __init__(self, n):
        self.fa = [i for i in range(n)]

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def merge(self, x, y):
        x_fa = self.find(x)
        y_fa = self.find(y)
        if x_fa != y_fa:
            self.fa[y_fa] = x_fa

m, n = map(int, input().split())
matrix = []
for i in range(n):
    matrix.append(list(map(int, input().split())))

ufs = UnionFindSet(n * m)

huawei = [] # 记录小华位置
restaurants = [] # 记录聚餐地点位置

offsets = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 偏移量

for i in range(n):
    for j in range(m):
        if matrix[i][j] != 1: # 如果是障碍物则不处理
            x = i * m + j # 将二维坐标转换为一维坐标
            if matrix[i][j] == 2:
                huawei.append(x) # 记录小华位置
            elif matrix[i][j] == 3:
                restaurants.append(x) # 记录聚餐地点位置
            for offset in offsets: # 遍历四个方向
                newI = i + offset[0]
                newJ = j + offset[1]
                if 0 <= newI < n and 0 <= newJ < m and matrix[newI][newJ] != 1:
                    ufs.merge(x, newI * m + newJ) # 合并连通块

hua_fa = ufs.find(huawei[0]) # 获取小华所在连通块的祖先
wei_fa = ufs.find(huawei[1]) # 获取小为所在连通块的祖先

if hua_fa != wei_fa: # 如果小华和小为不在同一个连通块中，说明没有共同到达的聚餐地点
    print(0)
else:
    ans = 0
    for restaurant in restaurants: # 遍历所有聚餐地点
        if ufs.find(restaurant) == hua_fa: # 如果聚餐地点和小华在同一个连通块中
            ans += 1 # 答案加一
    print(ans) # 输出答案

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

原文链接