0

囲碁ゲームでデッド ストーンをクリアするアルゴリズムを実装しようとしています。

再帰的に使用すると最も効率的で実装が簡単になるため、フラッドフィルがこれを達成するのに最適であると聞いています。

コード内での使用に問題があり、どのように実装すればよいのか疑問に思っていました。

これは私のクラスの 1 つです。

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はその他の文字

どんな助けでも素晴らしいでしょう！

4

4 に答える 4

2

他の答えは技術的には正しいですが、行くことに関連する多くのロジックが欠けています。あなたがする必要があるのは、私が思うに（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上記の場合、グループ内のすべての石を識別する塗りつぶしは次のようになります (グループを見つけるためだけに変更したくないため、塗りつぶしに 2 番目の配列を使用することに注意してください)。

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);
    }
}

これを呼び出して 1 つのグループを識別する (そしてそれをマスクにコピーする) ことができるので、(たとえば) B の移動に隣接する W グループのメンバーを識別するのに役立ちますが、それはロジック全体のごく一部にすぎません。あなたが必要です。

最後に、グループ内のすべての石で何かをしたい場合は、2 つのオプションがあることに注意してください。上記のようなルーチンを呼び出し、ループしmaskてグループを見つけるか、実行したいアクションをルーチン内に直接配置することができます (この場合でもmask、塗りつぶしの塗りつぶしの範囲を制御するために使用します)。テスト&& mask[x][y] == ' 'しますが、結果としてそれを使用しません - ルーチンが戻るまでにすべての作業が完了しています)。

(すべてのルールに従って正しく処理するためのプログラミングは、実際には非常に複雑です。多くの作業が必要です... :o)

于 2012-04-10T11:21:08.877 に答える
1

私はそのために虚偽の証拠を使用します。捕獲された石を見つける方法は次のとおりです。 

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)
于 2016-09-17T09:09:49.690 に答える
0

この場合は BFS の方が適していると思います。最初に近隣を探索する必要があり、それらのいずれかがキャプチャされた場合にポイントがキャプチャされるためです。

于 2017-02-10T17:37:05.370 に答える