重看了一下刘汝佳的白板书,上次写八皇后时并不是很懂,再写一次:
方法1:逐行放置皇后,然后递归;
代码:
1 #include <bits/stdc++.h> 2 #define MAXN 8 3 #define ll long long 4 using namespace std; 5 6 ll ans=0; 7 int c[MAXN]; 8 9 void dfs(int cur) 10 { 11 if(cur==MAXN) ans++; //***因为是逐行放置的,所以只要走到最后一行则肯定可行 12 else 13 { 14 for(int i=0; i<MAXN; i++) //***尝试在第cur行的第i列放置皇后 15 { 16 int flag=1; 17 c[cur]=i; 18 for(int j=0; j<cur; j++) 19 { 20 if(c[cur]==c[j]||c[cur]+cur==j+c[j]||c[cur]-cur==c[j]-j) //**判断皇后是否会相互攻击 21 { 22 flag=0; 23 break; 24 } 25 } 26 if(flag) 27 { 28 dfs(cur+1); //***如果合法,继续递归 29 } 30 } 31 } 32 } 33 34 int main(void) 35 { 36 dfs(0); 37 cout << ans << endl; 38 return 0; 39 }
方法2:思路和方法1差不多,区别是用二维数组vis[2][]来标记之前皇后的位置,判断是否会相互攻击
代码:
1 #include <bits/stdc++.h> 2 #define MAXN 8 3 #define ll long long 4 using namespace std; 5 6 ll ans=0; 7 int c[MAXN], vis[3][2*MAXN]; 8 9 void dfs(int cur) 10 { 11 if(cur==MAXN) ans++; //***因为是逐行放置的,所以只要走到最后一行则肯定可行 12 else 13 { 14 for(int i=0; i<MAXN; i++) 15 { 16 if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+MAXN]) 17 { 18 c[cur]=i; //***尝试将皇后放置在第cur行第i列 19 vis[0][i]=vis[1][cur+i]=vis[2][cur-i+MAXN]=1; //**标记 20 dfs(cur+1); //**递归 21 vis[0][i]=vis[1][cur+i]=vis[2][cur-i+MAXN]=0; //**去除标记 22 } 23 } 24 } 25 } 26 27 int main(void) 28 { 29 dfs(0); 30 cout << ans << endl; 31 return 0; 32 }