【华为OD机试真题】- 围棋的气(JS解答)

题目描述:
围棋棋盘由纵横各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。

JS参考解题：

解题思路:
这个问题可以通过模拟棋盘上棋子的放置和计算每个棋子的气来解决。为了方便计算每个棋子的气，我们可以创建一个棋盘数组(19x19)来表示整个棋盘，初始化时所有点都为空，然后根据输入放置黑棋和白棋。放置棋子后，我们遍历棋盘上的所有棋子，计算它们的气。
气的计算需要检查棋子上下左右四个方向的点是否为空，或者是否已经被计算过气（对于相连的同色棋子）。为了避免重复计算相连同色棋子群的气，我们可以使用一个查找算法（如深度优先搜索DFS）来标记访问过的同色棋子，并计算整个群的气。注意，在计算过程中我们使用了一个visited数组来防止对同一个棋子群的重复计算。

function calculateLiberties(black, white) {
    // 初始化19x19的棋盘，'.' 表示空位
    const board = Array.from(Array(19), () => Array(19).fill('.'));
    // 定义四个方向的移动，用于后面检查棋子的气
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

    // 放置棋子到棋盘上，黑棋或白棋
    function placeStones(stones, color) {
        for (let i = 0; i < stones.length; i += 2) {
            const x = stones[i];
            const y = stones[i + 1];
            board[x][y] = color;
        }
    }

    // 计算给定位置的棋子的气，采用DFS遍历同色棋子群，并计算气
    function countLiberties(x, y, visited) {
        // 如果该位置已访问过，返回0，避免重复计算
        if (visited[x][y]) return 0;
        visited[x][y] = true;
        // 如果是空位，直接返回1口气
        if (board[x][y] === '.') return 1;

        let liberties = 0; // 初始化气的数量
        const color = board[x][y]; // 当前棋子的颜色
        // 检查四个方向
        for (const [dx, dy] of directions) {
            const nx = x + dx, ny = y + dy;
            // 确保不越界
            if (nx >= 0 && nx < 19 && ny >= 0 && ny < 19) {
                if (board[nx][ny] === '.') liberties += 1; // 如果是空位，增加气的数量
                else if (board[nx][ny] === color) liberties += countLiberties(nx, ny, visited); // 如果是同色棋子，递归计算
            }
        }
        return liberties; // 返回计算得到的气的数量
    }

    // 放置黑棋和白棋
    placeStones(black.split(' ').map(Number), 'B');
    placeStones(white.split(' ').map(Number), 'W');

    let blackLiberties = 0, whiteLiberties = 0; // 初始化黑棋和白棋的气的数量
    const visited = Array.from(Array(19), () => Array(19).fill(false)); // 访问标记数组

    // 遍历棋盘上的每个位置
    for (let i = 0; i < 19; i++) {
        for (let j = 0; j < 19; j++) {
            // 如果当前位置有棋子，并且没有被访问过
            if (!visited[i][j] && board[i][j] !== '.') {
                const color = board[i][j]; // 获取棋子颜色
                // 对当前棋子所在的同色棋子群计算气，使用新的visited数组避免重复计算
                const liberties = countLiberties(i, j, Array.from(Array(19), () => Array(19).fill(false)));
                // 根据棋子颜色累加气的数量
                if (color === 'B') blackLiberties += liberties;
                else if (color === 'W') whiteLiberties += liberties;
            }
        }
    }

    return {blackLiberties, whiteLiberties}; // 返回黑棋和白棋的气的总数量
}

// 示例使用
const black = "0 5 8 9 9 10";
const white = "5 0 9 9 9 8";
console.log(calculateLiberties(black, white));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67