返回目录

题目描述

围棋棋盘由纵横各19条线垂直相交组成，棋盘上一共19 x 19 = 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

• 每行数据以空格分隔，数据个数是2的整数倍，每两个数是一组，代表棋子在棋盘上的坐标；
• 坐标的原点在棋盘左上角点，第一个值是行号，范围从0到18；第二个值是列号，范围从0到18。
• 举例说明：第一行数据表示三个坐标（0, 5）、(8, 9)、(9, 10)
• 第一行表示黑棋的坐标，第二行表示白棋的坐标。
• 题目保证输入两行数据，无空行且每行按前文要求是偶数个，每个坐标不会超出棋盘范围。

输出描述

8 7

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

用例

输入	0 0 5 8 9 9 10 5 0 9 9 9 8
输出	8 7
说明	数数黑棋一共8口气，数数白棋一共7口气。

题目解析

本题棋盘中“气”的位置有如下特点：

• 该位置没有棋子
• 该位置上下左右存在至少一个棋子（若为黑棋，则当前位置就是黑棋的气，若为白棋，则当前位置就是白棋的气，若既有黑棋，也有白棋，则同时为两个颜色棋的气）

因此，我们只需要遍历19*19的棋盘中每一个位置，检查对应位置是否有棋子，若没有棋子，则检查其上下左右四个位置是否存在黑棋、白棋，若存在则对应颜色的棋子的气数+1，需要注意的是，一个位置只能产生一个气，因此如果该位置的上下左右位置有多个黑棋，也只能为黑棋加一个气，白棋同理。

Python算法源码

class Board:
    def __init__(self):
        # 初始化棋盘，全部用0表示
        self.grid = [[0] * 19 for _ in range(19)]
        # 记录黑棋的气数
        self.black_liberties = 0
        # 记录白棋的气数
        self.white_liberties = 0

    def update_board(self, black_stones, white_stones):
        # 更新棋盘上的黑白棋子位置
        for i in range(0, len(black_stones), 2):
            x = black_stones[i]
            y = black_stones[i + 1]
            self.grid[x][y] = 1  # 用1表示黑棋

        for i in range(0, len(white_stones), 2):
            x = white_stones[i]
            y = white_stones[i + 1]
            self.grid[x][y] = 2  # 用2表示白棋

    def count_liberties(self):
        # 上下左右四个方向的偏移量
        offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))

        for i in range(19):
            for j in range(19):
                # 如果当前位置没有棋子，则可能是黑棋或白棋的气
                if self.grid[i][j] == 0:
                    is_black_liberty = False
                    is_white_liberty = False

                    # 检查当前位置的上下左右的位置
                    for offset_x, offset_y in offsets:
                        new_i = i + offset_x
                        new_j = j + offset_y

                        if 0 <= new_i < 19 and 0 <= new_j < 19:
                            is_black_liberty = is_black_liberty or (self.grid[new_i][new_j] == 1)
                            is_white_liberty = is_white_liberty or (self.grid[new_i][new_j] == 2)

                    # 若当前位置是黑棋的气，则黑棋气数加1
                    if is_black_liberty:
                        self.black_liberties += 1

                    # 若当前位置是白棋的气，则白棋气数加1
                    if is_white_liberty:
                        self.white_liberties += 1

    def get_liberties(self):
        # 计算黑白棋的气数并返回
        self.count_liberties()
        return f"{self.black_liberties} {self.white_liberties}"


def get_result(black_stones, white_stones):
    # 创建一个棋盘实例
    board = Board()
    # 更新棋盘上的黑白棋子位置
    board.update_board(black_stones, white_stones)
    # 获取黑白棋的气数并返回
    return board.get_liberties()


def main():
    # 获取输入的黑白棋子位置
    black_input = list(map(int, input().split()))
    white_input = list(map(int, input().split()))
    # 输出黑白棋的气数
    print(get_result(black_input, white_input))


if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>

#define MAX_SIZE 722
#define BOARD_SIZE 19

// 定义坐标结构体
struct Coordinate {
    int x;
    int y;
};

// 函数用于检查坐标是否在棋盘范围内
int isValidCoordinate(int x, int y) {
    return (x >= 0 && x < BOARD_SIZE && y >= 0 && y < BOARD_SIZE);
}

int main() {
    int black_stones[MAX_SIZE];
    int black_count = 0;

    // 读取黑棋坐标
    while (scanf("%d", &black_stones[black_count++])) {
        if (getchar() != ' ') break;
    }

    int white_stones[MAX_SIZE];
    int white_count = 0;

    // 读取白棋坐标
    while (scanf("%d", &white_stones[white_count++])) {
        if (getchar() != ' ') break;
    }

    // 用颜色表示棋子的棋盘
    int board[BOARD_SIZE][BOARD_SIZE] = {0};

    // 将黑棋放置在棋盘上
    for (int i = 0; i < black_count; i += 2) {
        int x = black_stones[i];
        int y = black_stones[i + 1];
        board[x][y] = 1; // 1表示黑棋
    }

    // 将白棋放置在棋盘上
    for (int i = 0; i < white_count; i += 2) {
        int x = white_stones[i];
        int y = white_stones[i + 1];
        board[x][y] = 2; // 2表示白棋
    }

    // 统计黑棋和白棋的气数
    int black_liberties = 0;
    int white_liberties = 0;

    // 定义相邻位置的偏移量
    int offsets[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 遍历棋盘计算气数
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            // 检查当前位置是否为空（无棋子）
            if (board[i][j] == 0) {
                // 用于跟踪黑棋和白棋的气数
                int black_liberty = 0;
                int white_liberty = 0;

                // 检查相邻位置是否有棋子
                for (int k = 0; k < 4; k++) {
                    int new_x = i + offsets[k][0];
                    int new_y = j + offsets[k][1];

                    // 检查新位置是否在棋盘范围内
                    if (!isValidCoordinate(new_x, new_y)) continue;

                    // 根据棋子颜色增加气数
                    if (board[new_x][new_y] == 1) black_liberty = 1;
                    if (board[new_x][new_y] == 2) white_liberty = 1;
                }

                // 更新黑棋和白棋的气数总数
                black_liberties += black_liberty;
                white_liberties += white_liberty;
            }
        }
    }

    // 输出黑棋和白棋的气数
    printf("%d %d", black_liberties, white_liberties);

    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();

        Counter count = processString(s);
        int ans = 0;
        int index = 0;

  
        while (index < s.length()) {
            if (s.charAt(index) == 'X') {
                count.countX++;
            } else {
                count.countY++;
            }

            if (count.countX == count.countY) {
                ans++;
            }

            index++;
        }

        System.out.println(ans);
    }

   
    static class Counter {
        int countX;
        int countY;
    }


    static Counter processString(String inputString) {
        /**
         * 处理输入字符串，返回一个包含 'X' 和 'Y' 数量的 Counter 对象。
         */
        Counter count = new Counter();
        for (int i = 0; i < inputString.length(); i++) {
            if (inputString.charAt(i) == 'X') {
                count.countX++;
            } else {
                count.countY++;
            }
        }
        return count;
    }
}