給定一個(gè)n*n的棋盤，棋盤中有一些位置不能放皇后。
現(xiàn)在要向棋盤中放入n個(gè)黑皇后和n個(gè)白皇后，使任意的兩個(gè)黑皇后都不在同一行、同一列或同一條對(duì)角線上，任意的兩個(gè)白皇后都不在同一行、同一列或同一條對(duì)角線上。
問(wèn)總共有多少種放法？
輸入的第一行為一個(gè)整數(shù)n，表示棋盤的大小。
接下來(lái)n行，每行n個(gè)0或1的整數(shù)，如果一個(gè)整數(shù)為1，表示對(duì)應(yīng)的位置可以放皇后，如果一個(gè)整數(shù)為0，表示對(duì)應(yīng)的位置不可以放皇后。
n小于等于8。
輸出一個(gè)整數(shù)，表示總共有多少種放法。
4 1111 1111 1111 1111 4 1011 1111 1111 1111 樣例輸出 2 0
探討2n皇后問(wèn)題之前，先看看N皇后問(wèn)題 用vis[3][] 標(biāo)記已經(jīng)訪問(wèn)過(guò)的縱，和兩個(gè)對(duì)角線。這樣復(fù)雜度就可以大大減低o(1)的時(shí)間內(nèi)可以判定是否可行。
對(duì)于縱排是否可以訪問(wèn)只要記錄那一縱的橫坐標(biāo)即可；對(duì)角線是直線，我們記錄他的截距即可。
說(shuō)了這么多，為什么我沒(méi)提到橫排的問(wèn)題，這個(gè)自己體會(huì)代碼吧，懶得打字了。
#include<stdio.h>#include<string.h>#define MAX_N 8bool map[MAX_N][MAX_N];bool vis[3][MAX_N*2];int N,ans;void dfs_1(int cnt){ if(cnt==N){ans++;return ;} for(int i=0;i<N;i++){ if(vis[0][i]||vis[1][i+cnt]||vis[2][N-cnt+i]) continue; vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=true; dfs_1(cnt+1); vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=false; }}int main(){ while(~scanf("%d",&N)){ for(int j=0;j<N;j++) for(int k=0;k<N;k++) scanf("%1d",&map[k][j]); ans=0; dfs_1(0); 在上面基礎(chǔ)上dfs再走一遍就解決2n皇后問(wèn)題了 //我把bool型的map寫(xiě)成char，因?yàn)檫@個(gè)WA了兩次，，，我也不知道原因，理論上是沒(méi)問(wèn)題的，不知道是oj的問(wèn)題還是數(shù)據(jù)的問(wèn)題#include<stdio.h>#include<string.h>#define MAX_N 20char map[MAX_N][MAX_N];bool vis[3][MAX_N*2];bool vis_0[3][MAX_N*2];bool used[MAX_N][MAX_N];int N,ans;void dfs_0(int cnt){ if(cnt==N){ans++;return ;} for(int i=0;i<N;i++){ if(vis_0[0][i]||vis_0[1][i+cnt]||vis_0[2][N-cnt+i]||used[cnt][i]||map[cnt][i]=='0') continue; vis_0[0][i]=vis_0[1][i+cnt]=vis_0[2][N-cnt+i]=true; dfs_0(cnt+1); vis_0[0][i]=vis_0[1][i+cnt]=vis_0[2][N-cnt+i]=false; }}void dfs_1(int cnt){ if(cnt==N){ dfs_0(0); return ;} for(int i=0;i<N;i++){ if(vis[0][i]||vis[1][i+cnt]||vis[2][N-cnt+i]||map[cnt][i]=='0') continue; used[cnt][i]=vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=true; dfs_1(cnt+1); used[cnt][i]=vis[0][i]=vis[1][i+cnt]=vis[2][N-cnt+i]=false; }}int main(){ while(~scanf("%d",&N)){ for(int j=0;j<N;j++) scanf("%s",map[j]); memset(vis,0,sizeof(vis)); memset(vis_0,0,sizeof(vis_0)); memset(used,0,sizeof(used)); ans=0; dfs_1(0); printf("%d/n",ans); } return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
