新乡网站建设设计,广州微网站建设dmz100,php网站制作软件,学做ppt的网站 免费下载设计一种算法#xff0c;打印 N 皇后在 N N 棋盘上的各种摆法#xff0c;其中每个皇后都不同行、不同列#xff0c;也不在对角线上。这里的“对角线”指的是所有的对角线#xff0c;不只是平分整个棋盘的那两条对角线。
注意#xff1a;本题相对原题做了扩展
示例:
输…设计一种算法打印 N 皇后在 N × N 棋盘上的各种摆法其中每个皇后都不同行、不同列也不在对角线上。这里的“对角线”指的是所有的对角线不只是平分整个棋盘的那两条对角线。
注意本题相对原题做了扩展
示例:
输入4 输出[[.Q…,…Q,“Q…”,…Q.],[…Q.,“Q…”,…Q,.Q…]] 解释: 4 皇后问题存在如下两个不同的解法。 [ [.Q…, // 解法 1 “…Q”, “Q…”, “…Q.”],
[…Q., // 解法 2 “Q…”, “…Q”, “.Q…”] ]
代码
class Solution {ListListString cListnew ArrayList();public ListListString solveNQueens(int n) {char[][] charsnew char[n][n];for(int i0;in;i)Arrays.fill(chars[i],.);//全部都没放皇后solveNQ(n,chars,0);return cList;}public void solveNQ(int n,char[][] chars,int row) {if(rown)//返回结果{ListString tempnew ArrayList();for(int i0;in;i){temp.add(String.valueOf(chars[i]));}cList.add(temp);return;}for(int i0;in;i)//选择列{if(isOk(i,chars,row)){chars[row][i]Q;solveNQ(n,chars,row1);//下一行chars[row][i].;//回溯}}}public boolean isOk(int col,char[][] chars,int row) {//检查位置是否合法for(int irow-1;i0;i--){if(chars[i][col]Q)return false;if(colrow-ichars.lengthchars[i][colrow-i]Q)return false;if(col-rowi0chars[i][col-rowi]Q)return false;}return true;}
}
