目录
34. N皇后问题 II
根据n皇后问题,现在返回n皇后不同的解决方案的数量而不是具体的放置布局。
样例 1:
输入: n=1
输出: 1
解释:
1:
1
样例 2:
输入: n=4
输出: 2
解释:
1:
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
2:
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
public class Solution { /**
* @param n: The number of queens.
* @return: The total number of distinct solutions.
*/ public int totalNQueens(int n) { // write your code here int[] map = new int[n]; Arrays.fill(map, -1); List<List<String>> ret = new ArrayList<>(); this.solveNQueens(map, 0, ret); return ret.size(); } private void solveNQueens(int[] map, int rowIndex, List<List<String>> ret) { if (rowIndex == map.length) { List<String> oneRet = new ArrayList<>(); for (int r = 0; r < map.length; r++) { StringBuilder sb = new StringBuilder(); for (int c = 0; c < map.length; c++) { if (map[r] == c) { sb.append("Q"); } else { sb.append("."); } } oneRet.add(sb.toString()); } ret.add(oneRet); return; } for (int c = 0; c < map.length; c++) { if (this.isValid(map, rowIndex, c)) { map[rowIndex] = c; this.solveNQueens(map, rowIndex + 1, ret); } } map[rowIndex] = -1; } private boolean isValid(int[] map, int rowIndex, int columnIndex) { for (int r = 0; r < rowIndex; r++) { if (map[r] == columnIndex) { return false; } if (Math.abs(rowIndex - r) == Math.abs(columnIndex - map[r])) { return false; } } return true; } }
鸣谢
非常感谢你愿意花时间阅读本文章,本人水平有限,如果有什么说的不对的地方,请指正。
欢迎各位留言讨论,希望小伙伴们都能每天进步一点点。
本文地址:https://blog.csdn.net/leyi520/article/details/107893821
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的,请 点击进行留言回复,万千网友为您解惑!
网友评论