游戏1.n皇后问题

nn的矩阵，需要每次选n个选择，选择n次，就是一个数每次都可以使用的全排列问题，但其实不是每次都需要选n次，而是要根据以前的选择来决定现在可以选什么。只是限制条件比一般的全排列问题更多。
所以先将一个nn的char表赋值为.,然后开始从第一行开始选，就是for循环这个数组，如果这个点符合标准，则递归开始选下一行，否则就跳过。如果最终发现遍历完最后一行，则将这个表加入res中继续回溯遍历。
检查这个值是否冲突，则需要检查这个值的上方列，左上方，右上方。

class Solution {List<List<String>> res=new ArrayList<List<String>>();public List<List<String>> solveNQueens(int n) {   char[][] c=new char[n][n];for(char[] s:c){Arrays.fill(s,'.');}dfs(n,c,0);return res;}public void dfs(int n,char[][] c,int index){if(index==n){List<String> list=new ArrayList<String>();for(int i=0;i<n;i++){list.add(String.valueOf(c[i]));}res.add(list);return;}for(int i=0;i<n;i++){if(isVaild(c,index,i)){c[index][i]='Q';dfs(n,c,index+1);c[index][i]='.';}}}public boolean isVaild(char[][] c,int i,int j){for(int t=0;t<i;t++){if(c[t][j]=='Q')return false;}for(int t=i-1,s=j-1;t>=0 && s>=0;t--,s--){if(c[t][s]=='Q')return false;}for(int t=i-1,s=j+1;t>=0 && s<c.length;t--,s++){if(c[t][s]=='Q')return false;}return true;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！