leetcode 51N皇后 52N皇后II 朱雀 2023-06-19 09:43 146阅读 0赞 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 示例: ![在这里插入图片描述][format_png] 输入: 4 输出: \[ \[".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”\], \["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”\] \] 解释: 4 皇后问题存在两个不同的解法。 思路： 回溯即可，回溯每一行，只是每填充一个Q，需要判断放入是否冲突了。 class Solution { int n = 0; public List<List<String>> solveNQueens(int n) { List<List<String>> list = new ArrayList<>(); if (n <= 0) { return list; } this.n = n; char[][] chars = new char[n][n]; for (int i = 0;i < n;i++) { for (int j = 0;j < n;j++) { chars[i][j] = '.'; } } dfs(list,chars,0); return list; } public void dfs (List<List<String>> list,char[][] chars,int start) { if (start == this.n ) { List<String> tmp = new ArrayList<>(); for (int i = 0;i < this.n;i++) { tmp.add(new String(chars[i])); } list.add(tmp); return; } for (int i = 0;i < n;i++) { chars[start][i] = 'Q'; if (isExist(chars,start,i)) { dfs(list,chars,start+1); } chars[start][i] = '.'; } } public boolean isExist(char[][] chars,int row,int col) { for (int i = 0;i < col;i++) { if (chars[row][i] == 'Q') return false; } for (int i = 0; i < row;i++) { if (chars[i][col] == 'Q') return false; } int j = col-1; for (int i = row-1;i >= 0 && j >= 0 ;) { if (chars[i][j] == 'Q') return false; i--; j--; } j = col+1; for (int i = row-1;i >= 0 && j < this.n; ) { if (chars[i][j] == 'Q') return false; i--; j++; } return true; } } leetcode 52 增加一个全局变量即可 class Solution { int n = 0; int count = 0; public int totalNQueens(int n) { if (n <= 0) { return count; } this.n = n; char[][] chars = new char[n][n]; for (int i = 0;i < n;i++) { for (int j = 0;j < n;j++) { chars[i][j] = '.'; } } dfs(chars,0); return count; } public void dfs (char[][] chars,int start) { if (start == this.n ) { this.count++; return; } for (int i = 0;i < n;i++) { chars[start][i] = 'Q'; if (isExist(chars,start,i)) { dfs(chars,start+1); } chars[start][i] = '.'; } } public boolean isExist(char[][] chars,int row,int col) { for (int i = 0;i < col;i++) { if (chars[row][i] == 'Q') return false; } for (int i = 0; i < row;i++) { if (chars[i][col] == 'Q') return false; } int j = col-1; for (int i = row-1;i >= 0 && j >= 0 ;) { if (chars[i][j] == 'Q') return false; i--; j--; } j = col+1; for (int i = row-1;i >= 0 && j < this.n; ) { if (chars[i][j] == 'Q') return false; i--; j++; } return true; } } [format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE4LzEwLzEyLzgtcXVlZW5zLnBuZw?x-oss-process=image/format,png
还没有评论，来说两句吧...