【hot100-java】N 皇后

回溯篇

视频题解 

真的裂开了，多看视频题解。

class Solution {
    public List<List<String>> solveNQueens(int n) {
           List<List<String>>ret=new ArrayList<>();
           int []col=new int[n];
           boolean[] onPath=new boolean[n];
           boolean[] diag1=new boolean[n*2-1];
           boolean[] diag2=new boolean[n*2-1];
           dfs(0,n,col,onPath,diag1,diag2,ret);
           return ret;
    }
    private void dfs(int r,int n,int[] col,boolean[] onPath,boolean[] diag1,boolean[] diag2,List<List<String>>ret){
        if(r==n){
            List<String>board=new ArrayList<>(n);
            for(int c:col){
                char[] row = new char[n];
                Arrays.fill(row,'.');
                row[c]='Q';
                board.add(new String(row));
            }
            ret.add(board);
            return;
        }
        
        for (int c=0;c<n;c++){
            int rc=r-c+n-1;
            if(!onPath[c]&&!diag1[r+c]&&!diag2[rc]){
                col[r]=c;
                onPath[c]=diag1[r+c]=diag2[rc]=true;
                dfs(r+1,n,col,onPath,diag1,diag2,ret);
                //恢复现场
                onPath[c]=diag1[r+c]=diag2[rc]=false;
            }
        }
    }
}