【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;}}}
}