Определите, являются ли два квадрата на доске смежными / соединенными квадратами одного и того же хода () - PullRequest
0 голосов
/ 28 марта 2020

Я написал код ниже, а также метод isAdjacentColor. Метод isAdjacentColor возвращает true, если два квадрата соседние (например, ферзь одного квадрата отходит друг от друга) и имеют одинаковый цвет или поворот ().

Я думаю, что реализовал поиск в ширину.

Мне было интересно, как использовать рекурсивный вызов, поскольку текущий возврат рекурсивного вызова вернет false до того, как будут исследованы все смежные параметры.

boolean isContiguous(Square from, Square to, boolean[][] visited) {
        if (get(from) != get(to)) {
            return false;
        }
        if (from == to) {
            return true;
        }
        int col = from.col();
        int row = from.row();
        if (!visited[col][row]) {
            visited[col][row] = true;
            if (col - 1 >= 0 && row - 1 >= 0) {
                Square curr = sq(col - 1, row - 1);
                if (isAdjacentColor(from, curr, turn())) {
                    return isContiguous(curr, to, visited);
                }
            }
            if (row - 1 >= 0) {
                Square curr = sq(col, row - 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    return isContiguous(curr, to, visited);
                }
            }
            if (col + 1 < BOARD_SIZE && row - 1 >= 0) {
                Square curr = sq(col + 1, row - 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    return isContiguous(curr, to, visited);
                }
            }
            if (col - 1 >= 0) {
                Square curr = sq(col - 1, row);
                if (isAdjacentColor(from, curr, get(from))) {
                    return isContiguous(curr, to, visited);
                }
            }
            if (col + 1 < BOARD_SIZE) {
                Square curr = sq(col + 1, row);
                if (isAdjacentColor(from, curr, get(from))) {
                    return isContiguous(curr, to, visited);
                }
            }
            if (col - 1 >= 0 && row + 1 < BOARD_SIZE) {
                Square curr = sq(col - 1, row + 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    return isContiguous(curr, to, visited);
                }
            }
            if (row + 1 < BOARD_SIZE) {
                Square curr = sq(col, row + 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    return isContiguous(curr, to, visited);
                }
            }
            if (col + 1 < BOARD_SIZE && row + 1 < BOARD_SIZE) {
                Square curr = sq(col + 1, row + 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    return isContiguous(curr, to, visited);
                }
            }
        }
        return false;
    }

1 Ответ

0 голосов
/ 28 марта 2020

Мне кажется, я решил свою проблему, создав ArrayList, в котором хранятся ответы на каждый рекурсивный вызов. Затем в конце вместо возврата false я возвращаю, если ArrayList содержит true.

    boolean isContiguous(Square from, Square to, boolean[][] visited) {
        if (get(from) != get(to)) {
            return false;
        }
        if (from == to) {
            return true;
        }
        int col = from.col();
        int row = from.row();
        if (!visited[col][row]) {
            visited[col][row] = true;
            if (col - 1 >= 0 && row - 1 >= 0) {
                Square curr = sq(col - 1, row - 1);
                if (isAdjacentColor(from, curr, turn())) {
                    contain.add(isContiguous(curr, to, visited));
                }
            }
            if (row - 1 >= 0) {
                Square curr = sq(col, row - 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    contain.add(isContiguous(curr, to, visited));
                }
            }
            if (col + 1 < BOARD_SIZE && row - 1 >= 0) {
                Square curr = sq(col + 1, row - 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    contain.add(isContiguous(curr, to, visited));
                }
            }
            if (col - 1 >= 0) {
                Square curr = sq(col - 1, row);
                if (isAdjacentColor(from, curr, get(from))) {
                    contain.add(isContiguous(curr, to, visited));
                }
            }
            if (col + 1 < BOARD_SIZE) {
                Square curr = sq(col + 1, row);
                if (isAdjacentColor(from, curr, get(from))) {
                    contain.add(isContiguous(curr, to, visited));
                }
            }
            if (col - 1 >= 0 && row + 1 < BOARD_SIZE) {
                Square curr = sq(col - 1, row + 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    contain.add(isContiguous(curr, to, visited));
                }
            }
            if (row + 1 < BOARD_SIZE) {
                Square curr = sq(col, row + 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    contain.add(isContiguous(curr, to, visited));
                }
            }
            if (col + 1 < BOARD_SIZE && row + 1 < BOARD_SIZE) {
                Square curr = sq(col + 1, row + 1);
                if (isAdjacentColor(from, curr, get(from))) {
                    contain.add(isContiguous(curr, to, visited));
                }
            }
        }
        return contain.contains(true);
    }
...