JAVA - Go遊戲算法

Question

我想實現一個算法來清除我的Go遊戲中的死亡石頭。

聽說floodfill是最好的實現這是使用它遞歸將是最effiecient也更容易實現。

我在使用它在我的代碼中的麻煩，想知道我應該怎麼去實現它。

這是我的一個類，它很自我解釋。

import java.io.*; 

public class GoGame implements Serializable { 

    int size; 
    char[][] pos; // This is the array that stores whether a Black (B) or White (W) piece is stored, otherwise its an empty character. 

    public GoGame(int s){ 
     size = s; 
    } 

    public void init() { 
     pos = new char[size][size]; 
     for (int i=0;i<size;i++) { 
      for (int j=0;j<size;j++) { 
       pos[i][j] = ' '; 
      } 
     } 
    } 

    public void ClearAll() { 
     for (int i=0;i<size;i++) { 
      for (int j=0;j<size;j++) { 
       pos[i][j] = ' '; 
      } 
     } 
    } 

    public void clear(int x, int y) { 
     pos[x][y]=' '; 
    } 

    public void putB(int x, int y) { //places a black stone on the board+array 
     pos[x][y]='B'; 
     floodfill(x,y,'B','W'); 

    } 

    public void putW(int x, int y) { //places a white stone on the board+array 
     pos[x][y]='W'; 
     floodfill(x,y,'W','B'); 

    } 

    public char get(int x, int y) { 
     return pos[x][y]; 
    } 

    public void floodfill(int x, int y, char placed, char liberty){ 


     floodfill(x-1, y, placed, liberty); 
     floodfill(x+1, y, placed, liberty); 
     floodfill(x, y-1, placed, liberty); 
     floodfill(x, y+1, placed, liberty); 

    } 

} 

x和y是方形的座標，placed是石頭的性格放下，liberty是其他字符

任何幫助將是驚人的！

Answer 1

而其他答案在技術上是正確的，你也錯過了更多的邏輯去相關。你需要做的是，我認爲（在b移動）：

for each W neighbour of the move: 
    check that W group to see if it has any liberties (spaces) 
     remove it if not 

洪水填充是找到一組石頭的上是有用的，但你的日常需要的不僅是多了不少（我在這裏簡化，並試圖猜測這個例程用於什麼 - 請參閱下面的評論）。

鑑於上述情況，標識組中所有石塊的填充填充將是這樣的（請注意，它使用第二個填充數組，因爲您不想更改pos只是爲了找到組）：

public void findGroup(int x, int y, char colour, char[][] mask) { 
    // if this square is the colour expected and has not been visited before 
    if (pos[x][y] == colour && mask[x][y] == ' ') { 
     // save this group member 
     mask[x][y] = pos[x][y]; 
     // look at the neighbours 
     findGroup(x+1, y, colour, mask); 
     findGroup(x-1, y, colour, mask); 
     findGroup(x, y+1, colour, mask); 
     findGroup(x, y-1, colour, mask); 
    } 
} 

你可以調用識別單個組（並將其複製到面罩），所以它會幫助你確定一個W基團是鄰居b移動（例如）的成員，但它只是您需要的全部邏輯的一小部分。

最後，請注意，如果你想要做的事與組中的每一塊石頭，你有兩個選擇。您可以調用類似上面的例程，然後循環使用mask來查找組，或者您可以將要執行的操作直接放入例程中（在這種情況下，仍然使用mask來控制洪泛填充的範圍在測試&& mask[x][y] == ' '中，但是你並沒有使用它 - 所有的工作都是在例程返回的時候完成的）。

（編程的東西去處理正確，下面所有的規則，其實是相當複雜的 - 你有很多工作要做...：O）

Answer 2

我會使用虛假證明了點。這是我如何找到拍攝的寶石：

private static final int SIZE = 8; 
private static final int VACANT = 0;  //empty point 
private static final int MY_COLOR = 1;  //Black 
private static final int ENEMY_COLOR = 2; //White 
private static final int CHECKED = 50;  //Mark for processed points 
private static final int OUT = 100;  //points out of the board 

private static boolean isCaptured(int col, int row, int[][] board) { 
    boolean result = !isNotCaptured(col, row, board); 
    cleanBoard(board); 
    return result; 
} 

private static boolean isNotCaptured(int col, int row, int[][] board) { 
    int value = board[col][row]; 
    if (!(value == MY_COLOR || value == CHECKED)) 
     return true; 

    int top = row < SIZE - 1 ? board[col][row + 1] : OUT; 
    int bottom = row > 0 - 1 ? board[col][row - 1] : OUT; 
    int left = col > 0 ? board[col - 1][row] : OUT; 
    int right = col < SIZE - 1 ? board[col + 1][row] : OUT; 

    if (top == VACANT || right == VACANT || left == VACANT || bottom == VACANT) 
     return true; 

    board[col][row] = CHECKED; 

    return (top == MY_COLOR && isNotCaptured(col, row + 1, board)) 
      || (bottom == MY_COLOR && isNotCaptured(col, row - 1, board)) 
      || (left == MY_COLOR && isNotCaptured(col - 1, row, board)) 
      || (right == MY_COLOR && isNotCaptured(col + 1, row, board)); 
} 

private static void cleanBoard(int[][] board) { 
    for (int i = 0; i < SIZE; i++) { 
     for (int j = 0; j < SIZE; j++) { 
      if (board[i][j] == CHECKED) 
       board[i][j] = MY_COLOR; 
     } 
    } 
} 

然後就可以調用的方法是這樣的：

isCaptured(5, 4, board) 

Answer 3

我認爲，BFS將是這種情況下更好，因爲你需要先探索鄰居，所以如果它們中的任何一個被捕獲，則該點被捕獲。