Leetcode - N Queues II

1306 ワード

[分析]N皇后第一题を终えて、これはso easy~

public class Solution {
    public int totalNQueens(int n) {
        int[] rows = new int[n]; // rows[i] = j, means board[i][j] = Q
        int[] cols = new int[n]; // cols[j] = i, means board[i][j] = Q
        for (int i = 0; i < n; i++) {
            rows[i] = -1;
            cols[i] = -1;
        }
        return recur(n, 0, rows, cols);
    }
    
    public int recur(int n, int r, int[] rows, int[] cols) {
        if (r == n) {
            return 1;
        }
        int result = 0;
        for (int j = 0; j < n; j++) {
            if (cols[j] == -1 && verifyDiagnal(rows, r, j)) {
                rows[r] = j;
                cols[j] = r;
                result += recur(n, r + 1, rows, cols);
                rows[r] = -1;
                cols[j] = -1;
            }
        }
        return result;
    }
    
    public boolean verifyDiagnal (int[] rows, int r, int c) {
        for (int i = 0; i < r; i++) {
            if (r - i == Math.abs(c - rows[i]))
                return false;
        }
        return true;
    }
}