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将是这种情况下更好，因为你需要先探索邻居，所以如果它们中的任何一个被捕获，则该点被捕获。