魔法棋盘

// 思路：由于Java Stream不太适合这种复杂的递归和回溯问题，因此这里依然采用传统方法。

public class MagicResonanceStream {
    private int n, m;
    private char[][] board;
    private int count = 0;

    public int solve(int n, int m, String[] chessboard) {
        this.n = n;
        this.m = m;
        this.board = new char[n][m];
        for (int i = 0; i < n; i++) {
            board[i] = chessboard[i].toCharArray();
        }
        backtrack(0, 0);
        return count;
    }

    private void backtrack(int i, int j) {
        if (i == n) {
            count++;
            return;
        }
        int ni = j == m - 1 ? i + 1 : i;
        int nj = j == m - 1 ? 0 : j + 1;
        if (board[i][j] == '?') {
            board[i][j] = '.';
            backtrack(ni, nj);
            board[i][j] = 'B';
            if (!hasResonance(i, j, 'B')) backtrack(ni, nj);
            board[i][j] = 'R';
            if (!hasResonance(i, j, 'R')) backtrack(ni, nj);
            board[i][j] = '?';
        } else {
            if (!hasResonance(i, j, board[i][j])) backtrack(ni, nj);
        }
    }

    private boolean hasResonance(int i, int j, char piece) {
        for (int k = 0; k < n; k++) {
            if (k != i && board[k][j] != '.' && board[k][j] != '?') {
                if (board[k][j] != piece && Math.abs(k - i) == 2) return true;
            }
        }
        for (int k = 0; k < m; k++) {
            if (k != j && board[i][k] != '.' && board[i][k] != '?') {
                if (board[i][k] != piece && Math.abs(k - j) == 2) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        MagicResonanceStream solver = new MagicResonanceStream();
        System.out.println(solver.solve(3, 3, new String[]{"..R", "..B", "?R?"})); // 5
        System.out.println(solver.solve(3, 3, new String[]{"?R?", "B?B", "?R?"})); // 105
    }
}