題目地址：http://www.51cpc.com/web/problem.php?id=1172

?

Summarize：

1. 遞歸回溯；

2. 先掃完一種皇后，再掃描另一種；

3. 循環(huán)輸入；

4. 每列每種皇后必有一個(gè)，依次搜索；

?

附代碼：

/* 2018-07-24 2n皇后 -回溯每列必有一黑一白兩個(gè)皇后，依次搜索； 將其中一種皇后放置完后，放置第二種皇后； */ #include<iostream> #include<cmath> using namespace std;#define LL long long const int N = 8+2; int n, vis[N][N]; LL ans=0;bool check(int x, int y, int queen) {if(vis[x][y] != 1) return false;if(x<0 || x>=n || y<0 || y>=n) return false;for(int i=0; i<n; i++) {if(vis[x][i] == queen || vis[i][y] == queen)return false;if(vis[x+i][y+i] == queen && x+i<n && y+i<n || vis[x-i][y-i] == queen && x>=i && y>=i|| vis[x+i][y-i] == queen && y>=i && x+i<n || vis[x-i][y+i] == queen && x>=i && y+i<n)return false;}return true; }void bqueen(int x) //3 - black {if(x == n) {ans++;return;}for(int i=0; i<n; i++){if(!check(x, i, 3)) continue;vis[x][i] = 3;bqueen(x+1);vis[x][i] = 1;} }void wqueen(int x) //2 - white {if(x == n) {bqueen(0);return;}for(int i=0; i<n; i++){if(!check(x, i, 2)) continue;vis[x][i] = 2;wqueen(x+1);vis[x][i] = 1;} }int main() {ios::sync_with_stdio(false);while(cin>>n){for(int i=0; i<n; i++)for(int j=0; j<n; j++)cin>>vis[i][j];ans=0;if(n) wqueen(0);cout<<ans<<endl;}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/liubilan/p/9370474.html

總結(jié)

以上是生活随笔為你收集整理的2n皇后 - 回溯的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。