【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【哈希集合】2023C-围棋的气【欧弟算法】全网注释最详细分类最全的华为OD真题题解

���LeetCode算法/华为OD考试扣扣交流群可加 948025485

可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题

绿色聊天软件戳 od1336了解算法冲刺训练

文章目录

• 题目描述与示例
• • 题目描述
  • 输入描述
  • 输出描述
  • 示例
  • • 输入
    • 输出
    • 解题思路
    • 代码
    • • Python
      • Java
      • C++
      • 时空复杂度
      • 华为OD算法/大厂面试高频题算法练习冲刺训练

        题目描述与示例

        题目描述

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

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

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

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

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

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

        输入描述

        输入包括两行数据，如:

        0 5 8 9 9 105 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 105 0 9 9 9 8

        输出

        8 7

        解题思路

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

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

        由于如例子所示的多个同色棋子共有气的情况的出现，假设某一个空位(ni, nj)是黑棋的共有气，为了不被重复计算，我们需要将(i, j)存入一个哈希集合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()来计算气的个数

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

        代码

        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     // 上下左右四个方向的偏移量数组    static int[][] D = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};    // 本函数用于计算某种颜色的气的个数    static int calQiNum(HashSet        // 构建气的哈希集合        HashSet            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                     // 此时近邻点为一个气，加入哈希集合 setQi 中                    setQi.add(new Pair        // 输入数据        Scanner scanner = new Scanner(System.in);        String blackInput = scanner.nextLine();        String whiteInput = scanner.nextLine();                // 解析输入数据        HashSet            int x = blackScanner.nextInt();            int y = blackScanner.nextInt();            setBlack.add(new Pair            int x = whiteScanner.nextInt();            int y = whiteScanner.nextInt();            setWhite.add(new Pair        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