最近看到一個題目挺有趣：「圍棋中的「被提取數」指的是某一方的棋子被對方提取（吃掉）的數量。在這樣的問題中，通常需要計算一方被提取的總數量，這涉及到棋子連接的判斷以及氣（自由度）的計算。」，這有點像DFS相關的題目，趁著記憶猶新來記錄一下。

題目

假設題目是這樣：

給定一個 N x N 的圍棋棋盤，我們用 ‘B’ 代表黑棋，用 ‘W’ 代表白棋，用 ‘.’ 代表空格。當某一方的棋子被包圍且沒有氣時，該棋子或整個連接的棋子組會被提取。我們需要計算出黑棋和白棋各自被提取的棋子數量。

範例輸入：

1
2
3
4
5
6
board = [
    ['B', 'B', 'W', '.'],
    ['B', 'W', 'W', '.'],
    ['.', 'W', 'B', 'B'],
    ['.', '.', 'B', 'B']
]

範例輸出：

1
2
黑棋被提取數: 1
白棋被提取數: 0

＊在圍棋中空白代表氣，如果棋子相鄰之間沒有空白並且被圍住，那就代表沒有氣。

解法思路：
我們可以透過DFS進行搜索，建立同等大小的Map去紀錄這條路徑是否有被走過，以便未來可以跳過，除此之外我們判斷前後左右是否有氣，如果沒有氣代表可能被圍住或是附近有相同顏色的棋子，此時我們可以進行紀錄，直到附近都被我們確認完是否有氣並且是由其他顏色所佔領，那就代表可以提取這些算過的棋子，反之直到最後發現有氣那就不需要被提取。

重點整理一下：
1.DFS探索：使用深度優先搜尋來尋找連接的棋子組（同色棋子連再一起的區域）。
2.計算氣：在搜尋的過程中，檢查該連接的棋子是否有氣。如果沒有氣，則該棋子組會被提取。
3.計數：對於每個沒有氣的棋子組，計算該組的棋子數量，並累加到該色的提取數。

同樣的我使用Javascript來實現：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import debug from 'debug';

const log = debug('algorithm');

function countCapturedStones(board) {
  // do algorithm
}

const board = [
    ['B', 'B', 'W', '.'],
    ['B', 'W', 'W', '.'],
    ['.', 'W', 'B', 'B'],
    ['.', '.', 'B', 'B']
]

const result = this.countCapturedStones(board);
log(`黑棋被提取數量：${result.blackCaptured}`);
log(`白棋被提取數量：${result.whiteCaptured}`);

處理好基本的內容，我們接著針對countCapturedStones去處理，首先我們先建立二維陣列並且紀錄當前是否被拜訪過，最後再回傳黑白棋被提取的數：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function countCapturedStones(board) {
  // N x N 的棋盤
  const N = board.length;
  // 建立一個二維陣列，並且我們把它填滿false，象徵我們目前還沒拜訪過此棋
  const visited = Array.from({ length: N }, () => Array(N).fill(false));

  let blackCaptured = 0;
  let whiteCaptured = 0;

  return {
    blackCaptured,
    whiteCaptured
  }
}

接著我們建立一個方向主要是去判斷周圍是否有氣，接著讓棋盤去跑動態路徑。

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
function countCapturedStones(board) {
  // N x N 的棋盤
  const N = board.length;
  // 建立一個二維陣列，並且我們把它填滿false，象徵我們目前還沒拜訪過此棋
  const visited = Array.from({ length: N }, () => Array(N).fill(false));

  let blackCaptured = 0;
  let whiteCaptured = 0;

  // 這主要用來跑前後左右並且判斷是否有氣或同色
  const directions = [
    [1, 0], [-1, 0], [0, 1], [0, -1]
  ];

  function dfs(x, y, color) {
    // do dfs
  }

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      // 判斷當前的棋子是否為氣或者已經被拜訪過
      if (board[i][j] !== '.' && !visited[i][j]) {
        // W or B
        const color = board[i][j];
        // 拿這個顏色棋子去跑dfs，並且回傳我們總共可以提取多少棋子
        const capturedStones = dfs(i, j, color);

        // 最後我們把提取回來的數量累加到對應顏色的棋子
        if (color === 'B') {
          blackCaptured += capturedStones;
        } else if (color === 'W') {
          whiteCaptured += capturedStones;
        }
      }
    }
  }

  return {
    blackCaptured,
    whiteCaptured
  }
}

接著我們開始做dfs：

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
function dfs(x, y, color) {
  // 這邊是預計要被判斷的地方
  let stack = [[x, y]];
  // 這邊是紀錄有哪些棋子，
  // 如果未來我們需要提取有哪些是被提走的可以使用這個
  let stones = [];
  // 預設沒有氣
  let hasLiberty = false;

  // 如果待判斷的數組還有資料，那就代表似乎還有連接的棋子
  // 我們必須要繼續去尋找值到判斷沒有氣（代表待判斷已空）
  while (stack.length > 0) {
    // 提取一個數組
    const [cx, cy] = stack.pop();
    // 這代表已經被拜訪過了，或者已經被計算完，我們可以直接跳過
    if (visited[cx][cy]) continue;

    visited[cx][cy] = true;
    // 放到紀錄表中
    stones.push([cx, cy]);

    // 判斷前後左右是否同色或有氣
    for (const [dx, dy] of  directions) {
      const nx = cx + dx;
      const ny = cx + dy;

      // 避免我們跑出棋盤之外，所以需要加個基本的判斷
      if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
        // 代表這有氣，所以我們基本上被提取就是0
        if (board[nx][ny] !== '.') {
          hasLiberty = true;
        } else if (board[nx][ny] === color && !visited[nx][ny]) {
          // 沒有被拜訪外過，相鄰的竟然是同族(X)同色好朋友，
          // 此時我們可以把他加入到下一次的檢查名單，
          stack.push([nx, ny]);
        }
      }
    }
  }

  if (!hasLiberty) {
    // 沒氣，我們可以安心的把這些成果提取走
    return stones.length;
  } else {
    // 有氣，代表沒被圍住，所以不需要被提取
    return 0;
  }
}

最後我們歸納一下程式：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
function countCapturedStones(board) {
  // N x N 的棋盤
  const N = board.length;
  // 建立一個二維陣列，並且我們把它填滿false，象徵我們目前還沒拜訪過此棋
  const visited = Array.from({ length: N }, () => Array(N).fill(false));

  let blackCaptured = 0;
  let whiteCaptured = 0;

  // 這主要用來跑前後左右並且判斷是否有氣或同色
  const directions = [
    [1, 0], [-1, 0], [0, 1], [0, -1]
  ];

  function dfs(x, y, color) {
    // 這邊是預計要被判斷的地方
    let stack = [[x, y]];
    // 這邊是紀錄有哪些棋子，
    // 如果未來我們需要提取有哪些是被提走的可以使用這個
    let stones = [];
    // 預設沒有氣
    let hasLiberty = false;

    // 如果待判斷的數組還有資料，那就代表似乎還有連接的棋子
    // 我們必須要繼續去尋找值到判斷沒有氣（代表待判斷已空）
    while (stack.length > 0) {
      // 提取一個數組
      const [cx, cy] = stack.pop();
      // 這代表已經被拜訪過了，或者已經被計算完，我們可以直接跳過
      if (visited[cx][cy]) continue;

      visited[cx][cy] = true;
      // 放到紀錄表中
      stones.push([cx, cy]);

      // 判斷前後左右是否同色或有氣
      for (const [dx, dy] of  directions) {
        const nx = cx + dx;
        const ny = cx + dy;

        // 避免我們跑出棋盤之外，所以需要加個基本的判斷
        if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
          // 代表這有氣，所以我們基本上被提取就是0
          if (board[nx][ny] !== '.') {
            hasLiberty = true;
          } else if (board[nx][ny] === color && !visited[nx][ny]) {
            // 沒有被拜訪外過，相鄰的竟然是同族(X)同色好朋友，
            // 此時我們可以把他加入到下一次的檢查名單，
            stack.push([nx, ny]);
          }
        }
      }
    }

    if (!hasLiberty) {
      // 沒氣，我們可以安心的把這些成果提取走
      return stones.length;
    } else {
      // 有氣，代表沒被圍住，所以不需要被提取
      return 0;
    }
  }

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      // 判斷當前的棋子是否為氣或者已經被拜訪過
      if (board[i][j] !== '.' && !visited[i][j]) {
        // W or B
        const color = board[i][j];
        // 拿這個顏色棋子去跑dfs，並且回傳我們總共可以提取多少棋子
        const capturedStones = dfs(i, j, color);

        // 最後我們把提取回來的數量累加到對應顏色的棋子
        if (color === 'B') {
          blackCaptured += capturedStones;
        } else if (color === 'W') {
          whiteCaptured += capturedStones;
        }
      }
    }
  }

  return {
    blackCaptured,
    whiteCaptured
  }
}

後記

如此一來我們就完成該題目，老實說挺有趣的，做了一些類似題目，沒想過圍棋也是一種動態規劃，為了不浪費重複運算，透過 visited 去略過一些不必要的運算並加快整體處理的速度。

比較類似的題目大概會像是：Leetcode 130 and 200，這兩個都是透過DFS/BFS來去計算，有興趣可以去嘗試看看。

以上，那我們下次見！