企业官网建设流程全解析

网站文字链接,免费微信网站制作平台,wordpress卡蜜 插件,网页制作工具 免费题目描述 51. N 皇后 - 力扣#xff08;LeetCode#xff09; 按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整数…题目描述51. N 皇后 - 力扣LeetCode按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将n个皇后放置在n×n的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数n返回所有不同的n皇后问题的解决方案。每一种解法包含一个不同的n 皇后问题的棋子放置方案该方案中Q和.分别代表了皇后和空位。示例 1输入n 4输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]解释如上图所示4 皇后问题存在两个不同的解法。示例 2输入n 1输出[[Q]]代码思路class Solution { public ListListString solveNQueens(int n) { ListListString result new ArrayList(); // 创建棋盘初始全为. char[][] board new char[n][n]; for (char[] row : board) { Arrays.fill(row, .); } // 从第0行开始回溯 backtrack(result, board, 0, n); return result; } private void backtrack(ListListString result, char[][] board, int row, int n) { // 终止条件已经成功放置了n个皇后 if (row n) { result.add(boardToList(board)); return; } // 尝试在当前行的每一列放置皇后 for (int col 0; col n; col) { // 检查当前位置(row, col)是否可以放置皇后 if (isValid(board, row, col, n)) { // 做选择放置皇后 board[row][col] Q; // 递归处理下一行 backtrack(result, board, row 1, n); // 撤销选择回溯 board[row][col] .; } } } private boolean isValid(char[][] board, int row, int col, int n) { // 检查同一列是否有皇后从第0行检查到当前行的上一行 for (int i 0; i row; i) { if (board[i][col] Q) { return false; // 同一列有皇后冲突 } } // 检查左上方对角线是否有皇后 // 对角线上的坐标特点行索引和列索引同时递减 for (int i row - 1, j col - 1; i 0 j 0; i--, j--) { if (board[i][j] Q) { return false; // 左上方对角线有皇后冲突 } } // 检查右上方对角线是否有皇后 // 对角线上的坐标特点行索引递减列索引递增 for (int i row - 1, j col 1; i 0 j n; i--, j) { if (board[i][j] Q) { return false; // 右上方对角线有皇后冲突 } } // 不需要检查同一行因为我们是逐行放置的 return true; // 所有检查都通过可以放置 } private ListString boardToList(char[][] board) { ListString list new ArrayList(); for (char[] row : board) { list.add(new String(row)); } return list; } }