围棋的气 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

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

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

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

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

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

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

示例1

输入：
0 5 8 9 9 10
5 0 9 9 9 8

输出：
8 7

题解

首先，我们需要理解围棋中的气是如何计算的。

题目中已经给出了相关的规则，根据这些规则，我们可以遍历每个棋子的上下左右四个相邻的位置，判断是否有气。

遍历所有同色的棋子，累加其气的数量。

Java

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

/**
 * @author code5bug
 */
public class Main {
    static int N = 19;
    static Scanner scanner = new Scanner(System.in);

    // 围棋棋盘
    static int[][] g = new int[N][N];
    // 位置四周坐标偏移量
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) {
        ArrayList<int[]> black = readInput(1);
        ArrayList<int[]> white = readInput(2);
        int bcnt = solve(black), wcnt = solve(white);
        System.out.println(bcnt + " " + wcnt);
    }

    // 读取棋子并安放到棋盘对应位置
    static ArrayList<int[]> readInput(int color) {
        ArrayList<int[]> locations = new ArrayList<>();

        String[] splits = scanner.nextLine().split(" ");
        for (int i = 0; i < splits.length; i += 2) {
            int r = Integer.parseInt(splits[i]);
            int c = Integer.parseInt(splits[i + 1]);
            locations.add(new int[]{r, c});
            g[r][c] = color;
        }
        return locations;
    }

    // 判断是否在棋盘内部
    static boolean valid(int r, int c) {
        return 0