时间戳

首页 > 解决方案 > 确定板上的两个方格是否由相同的方格连续/连接 turn()

java - 确定板上的两个方格是否由相同的方格连续/连接 turn()

问题描述

我编写了下面的代码以及 isAdjacentColor 方法。如果两个方格相邻（例如，一个方格的皇后彼此远离）并且具有相同的颜色或 turn()，则 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;
    }

标签： javarecursionbreadth-first-search

解决方案

我想我已经通过创建一个存储每个递归调用答案的 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);
    }

推荐阅读