题目
class Solution { List<List<String>>res; int n; boolean []col;//记录某列是否放置皇后 boolean []main1;//对角线 boolean []sub;//副对角线 public List<List<String>> solveNQueens(int n) { res=new ArrayList<>(); if(n==0)return res; this.n=n; this.col=new boolean[n]; this.main1=new boolean[2*n-1]; this.sub=new boolean[2*n-1]; Deque<Integer>path=new ArrayDeque<>();//双向队列 dfs(0,path); return res; } void dfs(int row,Deque<Integer>path){ if(row==n){ List<String>board=help(path); res.add(board); return; } for(int j=0;j<n;j++){//对于row行的每一列进行尝试 if(!col[j]&&!main1[row+j]&&!sub[row-j+n-1]){ path.addLast(j); col[j]=true; main1[row+j]=true; sub[row-j+n-1]=true; dfs(row+1,path); //回溯 sub[row-j+n-1]=false; main1[row+j]=false; col[j]=false; path.removeLast(); } } } List<String>help(Deque<Integer>path){ List<String>board=new ArrayList<>(); for(Integer num:path){ StringBuilder sb=new StringBuilder(); sb.append(".".repeat(Math.max(0,n))); sb.replace(num,num+1,"Q"); board.add(sb.toString()); } return board; } }