1213：八皇后問(wèn)題

時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 19355 ??? 通過(guò)數(shù): 6957

【題目描述】

在國(guó)際象棋棋盤上放置八個(gè)皇后，要求每?jī)蓚€(gè)皇后之間不能直接吃掉對(duì)方。

【輸入】

(無(wú))

【輸出】

按給定順序和格式輸出所有八皇后問(wèn)題的解（見(jiàn)樣例）。

【輸入樣例】

（無(wú)）

【輸出樣例】

No. 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 No. 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 ...以下省略

【分析】

? ? ? ? 縱向沖突檢查：遍歷行，判斷對(duì)應(yīng)column的值是否為1（沖突）。

? ? ? ? 左對(duì)角線沖突檢查：形狀為撇（丿），即行為row-1，列為column-1，行遞增，列遞減依次判斷。

? ? ? ? 右對(duì)角線沖突檢查：形狀為捺（?）類似左對(duì)角線。

? ? ? ? 這道題太坑了，輸出的時(shí)候要 i ,?j 轉(zhuǎn)換位置。

【參考代碼】

#include <stdio.h> #define QueenSize 8 //這個(gè)數(shù)等于幾，就是幾皇后。int num; // 8皇后可行解個(gè)數(shù) int chessboard[QueenSize][QueenSize]; // 棋盤 // 打印每種正確的解法 void outPut() {int i,j;num++;printf("No. %d\n",num);for(i=0;i<QueenSize;i++){for(j=0;j<QueenSize;j++){if(chessboard[j][i]==1) //這里太坑了printf("1 ");elseprintf("0 ");}printf("\n");}getchar(); }// 判斷皇后的落點(diǎn)是否合規(guī) int check(int row, int column) {int i,j;// 判斷縱向是否有沖突for(i=0;i<row;i++){if(chessboard[i][column])return 0;}// 判斷右對(duì)角線是否有沖突for(i=row-1,j=column-1;i>=0 && j>=0;i--,j--){if(chessboard[i][j]){return 0;}}// 判斷左對(duì)角線是否有沖突for(i=row-1,j=column+1;i>=0 && j<=QueenSize-1;i--,j++){if (chessboard[i][j]){return 0;}}return 1; }void dfs(int i) {int j;for(j=0;j<QueenSize;j++){chessboard[i][j]=1;if(check(i,j)){if(i+1==QueenSize){outPut();}else{dfs(i+1);}}chessboard[i][j] = 0; // 回溯 } }int main() {dfs(0);//printf("%d\n",num);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1213

?

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1213：八皇后问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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