题目描述与示例

题目描述

围棋棋盘由纵横各19条线垂直相交组成，棋盘上一共19x19=361个交点，对弈双方一方执白棋，一方执黑棋，落子时只能将棋子置于交点上。

“气”是围棋中很重要的一个概念，某个棋子有几口气，是指其上下左右方向四个相邻的交叉点中，有几个交又点没有棋子，由此可知：

1、在棋盘的边缘上的棋子最多有3口气（黑1），在棋盘角点的棋子最多有2口气（黑2），其它情况最多有4口气（白1）

img

2、所有同色棋子的气之和叫作该色棋子的气，需要注意的是，同色棋子重合的气点，对于该颜色棋子来说，只能计算一次气，比如下图中，黑棋一共4口气，而不是5口气，因为黑1和黑2中间红色三角标出的气，是两个黑棋共有的，对于黑棋整体来说只能算一个气。

img

3、本题目只计算气，对于眼也按气计算，如果您不清楚“眼”的概念，可忽略。按照前面描述的规则计算即可。

现在，请根据输入的黑棋和白棋的坐标位置，计算黑和白棋一共各有多少气?

输入描述

输入包括两行数据，如:

0 5 8 9 9 10
5 0 9 9 9 8

1、每行数据以空格分隔，数据个数是2的整数倍，每两个数是一组，代表棋子在棋盘上的坐标

2、坐标的原点在棋盘左上角点，第一个值是行号，范围从0到18；第二个值是列号，范围从0到18

3、举例说明：第一行数据表示三个坐标(0, 5)、(8, 9)、(9, 10)

4、第一行表示黑棋的坐标，第二行表示白棋的坐标。

5、题目保证输入两行数据，无空行且每行按前文要求是偶数个，每个坐标不会超出棋盘范围。

输出描述

8 7

两个数字以空格分隔，第一个数代表黑棋的气数，第二个数代表白棋的气数。

示例

输入

0 5 8 9 9 10
5 0 9 9 9 8

输出

8 7

解题思路

考虑正向的思路，即从棋子位置出发，计算每一个棋子上下左右的气的个数。

以黑棋为例（白棋是完全类似的）：

由于如例子所示的多个同色棋子共有气的情况的出现，假设某一个空位(ni, nj)是黑棋的共有气，为了不被重复计算，我们需要将(ni, nj)存入一个哈希集合black_qi_set中。那么，当下一次考虑到同一个空位(ni, nj)时，就不会多次储存了。

以黑棋为例，整体过程如下：

  1. 构建偏移数组D = [(0, 1), (1, 0), (0, -1), (-1, 0)]，构建哈希集合qi_set
  2. 遍历所有黑棋(i, j)
  3. 对于每一个黑棋的位置(i, j)，遍历偏移量(di, dj)，计算近邻点(ni, nj)
  4. 若(ni, nj)没有越界，且是空位（即既不为黑棋也不为白棋），则将(ni, nj)加入哈希集合qi_set中
  5. 所有遍历结束后，返回len(qi_set)即为黑棋的气的数量

由于白棋和黑棋计算气的过程是相似的，可以构造一个函数cal_qi_num()来计算气的个数

def cal_qi_num(set_color, set_other_color):
    set_qi = set()
    for i, j in set_color:
        for di, dj in D:
            ni, nj = i+di, j+dj
            if (0 <= ni <= 18 and 0 <= nj <= 18 and
                (ni, nj) not in set_color and (ni, nj) not in set_other_color):
                set_qi.add((ni, nj))
    return len(set_qi)

除了正向思路以外，本题还存在逆向的思路，即从所有空位出发，查看这个空位的周围是否存在黑棋或白棋。这种做法同样需要用到哈希集合来完成，感兴趣的同学可以尝试。

代码

Python

# 题目：【哈希集合】2023C-围棋的气
# 分值：100
# 作者：闭着眼睛学数理化-许老师
# 算法：哈希集合，模拟
# 代码看不懂的地方，请直接在群上提问


# 上下左右四个方向的偏移量数组
D = [(0, 1), (1, 0), (0, -1), (-1, 0)]


# set_color为某种颜色（黑或白）对应的棋子位置构成的哈希集合
# set_other_color对应另一种颜色的棋子位置构成的哈希集合
# 本函数用于计算该种颜色的气的个数
def cal_qi_num(set_color, set_other_color):
    # 构建气的哈希集合，之所以用哈希集合是为了共有气的去重
    set_qi = set()
    # 考虑所有同色棋子
    for i, j in set_color:
        # 遍历上下左右四个方位
        for di, dj in D:
            # 考虑近邻点(i, j)
            ni, nj = i+di, j+dj
            # 近邻点不越界，且为空位（既不是黑棋，也不是白棋）
            if (0 <= ni <= 18 and 0 <= nj <= 18 and
                (ni, nj) not in set_color and (ni, nj) not in set_other_color):
                # 此时近邻点为一个气，加入哈希集合set_qi中
                set_qi.add((ni, nj))
    # 返回哈希集合的长度，即为该种颜色的气的个数
    return len(set_qi)


# 输入数据
lst_black = list(map(int, input().split()))
lst_white = list(map(int, input().split()))

# 每两个数字为一组坐标，构建所有黑棋/白棋对应的哈希集合
set_black = set((lst_black[i], lst_black[i+1]) for i in range(0, len(lst_black), 2))
set_white = set((lst_white[i], lst_white[i+1]) for i in range(0, len(lst_white), 2))
# 分别调用cal_qi_num，计算黑棋和白棋的气的个数
ans_black = cal_qi_num(set_black, set_white)
ans_white = cal_qi_num(set_white, set_black)
# 输出答案
print(ans_black, ans_white)

Java

import java.util.*;

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

    // 本函数用于计算某种颜色的气的个数
    static int calQiNum(HashSet<Pair<Integer, Integer>> setColor, HashSet<Pair<Integer, Integer>> setOtherColor) {
        // 构建气的哈希集合
        HashSet<Pair<Integer, Integer>> setQi = new HashSet<>();
        // 考虑所有同色棋子
        for (Pair<Integer, Integer> p : setColor) {
            int i = p.first;
            int j = p.second;
            // 遍历上下左右四个方位
            for (int[] dir : D) {
                // 考虑近邻点 (i, j)
                int ni = i + dir[0];
                int nj = j + dir[1];
                // 近邻点不越界，且为空位（既不是黑棋，也不是白棋）
                if (0 <= ni && ni <= 18 && 0 <= nj && nj <= 18 &&
                        !setColor.contains(new Pair<>(ni, nj)) &&
                        !setOtherColor.contains(new Pair<>(ni, nj))) {
                    // 此时近邻点为一个气，加入哈希集合 setQi 中
                    setQi.add(new Pair<>(ni, nj));
                }
            }
        }
        // 返回哈希集合的大小，即为该种颜色的气的个数
        return setQi.size();
    }

    public static void main(String[] args) {
        // 输入数据
        Scanner scanner = new Scanner(System.in);
        String blackInput = scanner.nextLine();
        String whiteInput = scanner.nextLine();

        // 解析输入数据
        HashSet<Pair<Integer, Integer>> setBlack = new HashSet<>();
        HashSet<Pair<Integer, Integer>> setWhite = new HashSet<>();
        Scanner blackScanner = new Scanner(blackInput);
        Scanner whiteScanner = new Scanner(whiteInput);
        while (blackScanner.hasNext()) {
            int x = blackScanner.nextInt();
            int y = blackScanner.nextInt();
            setBlack.add(new Pair<>(x, y));
        }
        while (whiteScanner.hasNext()) {
            int x = whiteScanner.nextInt();
            int y = whiteScanner.nextInt();
            setWhite.add(new Pair<>(x, y));
        }

        // 分别调用 calQiNum，计算黑棋和白棋的气的个数
        int ansBlack = calQiNum(setBlack, setWhite);
        int ansWhite = calQiNum(setWhite, setBlack);
        // 输出答案
        System.out.println(ansBlack + " " + ansWhite);
    }

    // 自定义 Pair 类
    static class Pair<T, U> {
        T first;
        U second;

        Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }

        // 重写 equals 和 hashCode 方法
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) obj;
            return Objects.equals(first, pair.first) && Objects.equals(second, pair.second);
        }

        @Override
        public int hashCode() {
            return Objects.hash(first, second);
        }
    }
}

C++

“`C++
#include <iostream>
#include <unordered_set>
#include <utility>
#include <vector>
#include <sstream>

using namespace std;

// 自定义哈希函数
namespace std {
template <>
struct hash<pair<int, int>> {
size_t operator()(const pair<int, int>& p) const {
return hash<int>()(p.first) ^ hash<int>()(p.second);
}
};
}

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

// set_color为某种颜色（黑或白）对应的棋子位置构成的哈希集合
// set_other_color对应另一种颜色的棋子位置构成的哈希集合
// 本函数用于计算该种颜色的气的个数
int cal_qi_num(unordered_set<pair<int, int>>& set_color, unordered_set<pair<int, int>>& set_other_color) {
// 构建气的哈希集合，之所以用哈希集合是为了共有气的去重
unordered_set<pair<int, int>> set_qi;
// 考虑所有同色棋子
for (const auto& p : set_color) {
int i = p.first;
int j = p.second;
// 遍历上下左右四个方位
for (const auto& [di, dj] : D) {
// 考虑近邻点(i, j)
int ni = i + di;
int nj = j + dj;
// 近邻点不越界，且为空位（既不是黑棋，也不是白棋）
if (0 <= ni && ni <= 18 && 0 <= nj && nj <= 18 &&
set_color.find({ni, nj}) <span class="text-highlighted-inline" style="background-color: #fffd38;"> set_color.end() &&
set_other_color.find({ni, nj}) </span> set_other_color.end()) {
// 此时近邻点为一个气，加入哈希集合set_qi中
set_qi.insert({ni, nj});
}
}
}
// 返回哈希集合的大小，即为该种颜色的气的个数
return set_qi.size();
}

int main() {
// 输入数据
string blackInput, whiteInput;
getline(cin, blackInput);
getline(cin, whiteInput);
istringstream blackIss(blackInput), whiteIss(whiteInput);
unordered_set<pair<int, int>> set_black, set_white;

<pre><code>int x, y;
while (blackIss >> x >> y) {
set_black.insert({x, y});
}
while (whiteIss >> x >> y) {
set_white.insert({x, y});
}

// 分别调用cal_qi_num，计算黑棋和白棋的气的个数
int ans_black = cal_qi_num(set_black, set_white);
int ans_white = cal_qi_num(set_white, set_black);
// 输出答案
cout << ans_black << " " << ans_white << endl;

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(N+M)。需要遍历所有棋子，最多为O(391)

空间复杂度：O(N+M)。哈希集合所占空间，最多为O(391)

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）

上一篇 【哈希集合】2023Q1A-寻找密码
下一篇 【哈希表】2023Q1A-集五福

相关文章