May 5, 2022
N皇后
BV14Y4y1C7SW 以下是错误代码 / 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <bits/stdc++.h> using namespace std; int hash[10][10]; int cnt; void doAdd(int r, int c, int n, int val) { if (r < 0 || r >= n) { return ; } if (c < 0 || c >= n) { return ; } hash[r][c] += val; } void add(int r, int c, int n, int val) { int i; for (i = 0; i < n; i++) { doAdd(r, i, n, val); doAdd(i, c, r, val); } for (i = 0; i < n; i++) { doAdd(r + 1, c + 1, n, val) doAdd(r - 1, c - 1, n, val) doAdd(r + 1, c - 1, n, val) doAdd(r - 1, c + 1, n, val) } } void dfs(int depth, int maxDepth) { int i; if (depth == maxDepth) { ++cnt; return ; } for (i = 0; i < maxDepth; i++) { if (hash[depth][i] == 0) { add(depth, i, maxDepth, i); dfs(depth + 1, maxDepth); add(depth, i, maxDepth, -i) } } } int main() { int n; cin >> n; memset(hash, 0, sizeof(hash)); dfs(0, n); return cnt; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 package PACK6; // https://www.bilibili.com/video/BV14Y4y1C7SW public class N皇后 { // 首先定义一个哈希表 hash ij大于0 表示这个位置不能放皇后 static int[][] hash = new int[10][10]; // 定义全局变量cnt 表示方案数 static int cnt; public static void doADD(int r, int c, int n, int val) { // 如果行的范围越越界则标记无效 if (r < 0 || r >= n) { return; } // 如果列的范围越越界则标记无效 if (c < 0 || c >= n) { return; } // 如果对应位置是安全的，也就是没有皇后能够攻击到，则标记为1 // (否则在对应位置的hash数组执行标记) if (hash[r][c] == 0) { hash[r][c] = val; } } // 实现放置皇后的过程 public static void add(int r,int c ,int n,int val) { // val = 1; // 代表(r,c)位置放置了一个皇后 // val = -1; // 代表(r,c)位置取出了一个皇后 int i; for (i = 0; i < n; i++) { // 每放入一个皇后,需要将他所在的行，所在的列，所在的对角线 都进行标记 doADD(r, i, n, val); // 标记所在行 doADD(i, c, n, val); // 标记所在列 } for (i = 1; i <= n; i++) { // 标记主对角线 doADD(r + i, c + i, n, val); doADD(r - i, c - i, n, val); // 标记副对角线 doADD(r + i, c - i, n, val); doADD(r - i, c + i, n, val); } } public static void dfs(int depth, int maxDepth) { // 当前要放置的行号和总共要放置的行数 // 如果当前行数==总行数 方案数+1 函数直接返回 if (depth == maxDepth) { cnt++; return; } // 在当前行的每一列 for (int i = 0; i < maxDepth; i++) { // 如果发现有对应位置是安全的，也就是没有皇后能够攻击到， if (hash[depth][i] == 0) { // 则调用add放置一个皇后 add(depth, i, maxDepth, 1); // 递归求解下一行 dfs(depth + 1, maxDepth); // 递归退出后，删除放置的皇后(取回前面放置的皇后) add(depth, i, maxDepth, -1); } } } public static int fakeMain(int n) { // 初始化cnt = 0; cnt = 0; // 初始化hash ij = 0,表示一开始一个空的棋盘 for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { hash[i][j] = 0; } } // 递归模拟每一行放置皇后后的情况 dfs(0, n); return cnt; } public static void main(String[] args) { fakeMain(4); } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 class Solution { int hash[10][10]; int cnt; // 实现标记 void doAdd(int r, int c, int n, int val) { // 如果行的范围越界 则标记失败 if (r < 0 || r >= n) { return; } // 如果列的范围越界 则标记失败 if (c < 0 || c >= n) { return; } // 否则在对应的位置上的hash数组执行标记 hash[r][c] += val; } // 实现放置皇后的过程 void add(int r,int c,int n,int val) { int i; for (i = 0; i < n; i++) { doAdd(r,i,n,val); doAdd(i,c,r,val); } for (i = 0; i < n; i++) { // 标记主对角线 doAdd(r+i,c+i,n,val); doAdd(r-i,c-i,n,val); // 标记副对角线 doAdd(r+i,c-i,n,val); doAdd(r-i,c+i,n,val); } } void dfs(int depth, int maxDepth) { int i; if(depth == maxDepth) { ++cnt; return ; } for (i = 0; i < maxDepth; i++) { if(hash[depth][i] == 0) //对应位置安全，没有皇后能攻击到 { // 则调用add放置一个皇后 add(depth, i, maxDepth , 1); // 递归求解下一行 dfs(depth + 1, maxDepth); // 递归推出后，取出皇后 add(depth, i, maxDepth, -1); } } } public: int totalNQueens(int n) { cnt = 0; memset(hash, 0, sizeof(hash)); dfs(0,n); return cnt; } }
Read more