52. N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

思路：和I差不多

public class Solution {
    public int totalNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                board[i][j] = '.';
            }
        }

        List<List<String>> res = new ArrayList<List<String>>();
        List<String> temp = new ArrayList<String>();
        dfs(board,0,res,temp);
        return res.size();
    }

    public void dfs(char[][] board,int rowInd, List<List<String>> res, List<String> temp){
        if (rowInd==board.length){
            res.add(new ArrayList<String>(temp));
            return;
        }

        for (int i=0;i<board.length;i++){
            if (isValid(board,rowInd,i)){
                board[rowInd][i] = 'Q';
                String colStr = new String(board[rowInd]);
                temp.add(colStr);
                //System.out.println(colStr);
                dfs(board,rowInd+1,res,temp);
                board[rowInd][i] = '.';
                temp.remove(temp.size()-1);
            }
        }
    }

    public boolean isValid(char[][] board,int row,int col){
        for (int i=0;i<row;i++){
            for (int j=0;j<board.length;j++){
                if (board[i][j]=='Q'&&(row+j==col+i||row+col==i+j||col==j))
                    return false;
            }
        }
        return true;
    }
}