The Sultan's Successors UVA 167（八皇后問題）
來源：程序員人生 發(fā)布時間：2014-10-06 08:00:01 閱讀次數(shù)：3280次
說說：
其實這道題本質(zhì)上就是一個八皇后問題。唯一的區(qū)別就是每個棋盤的格子都對應一個數(shù)字。最后要求輸出，對應的解占據(jù)的格子的和的最大值。這只要在最后求出解的時候統(tǒng)計一下就可以了。下面就簡單的說說八皇后問題，其實解法也不難。因為要求每行每列都要有棋子。因此只要確定每一行對應的棋子的列數(shù)就可以了。而對于每個棋子的所放的位置，同列上和對角線上不能有其他棋子，這個只要設一個訪問數(shù)組保存一下就可以了。（注意要記得回溯）。至于對角線的表示方法，例如所在位置為（x，y），那么一條對角線可以用x+y表示，另一條對角線可以用x-y表示，但是由于數(shù)組的下標非負，因此可以將第二條對角線的值設為x-y+7，這樣就可以用一個二維數(shù)組來表示，一個相應的位置上能不能放棋子啦。具體的分析，請參見劉汝佳的《算法競賽入門經(jīng)典》P123
八皇后問題。
源代碼：
#include <stdio.h>
#include <string.h>
char vis[3][17];
int c[9];//存放每行的棋子所在的列數(shù)
int val[9][9];
int max,num=0;
void search(int);
int main(){
int k,i,j;
// freopen("data","r",stdin);
scanf("%d",&k);
while(k--){
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
scanf("%d",&val[i][j]);
memset(vis,0,sizeof(vis));
max=0;
search(1);
printf("%5d
",max);
}
return 0;
}
void search(int cur){
int i,sum;
if(cur>8){
sum=0;
for(i=1;i<=8;i++)
sum+=val[i][c[i]];
num++;
max=sum>max?sum:max;
}
else
for(i=1;i<=8;i++)
if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+7]){//同列，同對角線都沒有其他棋子
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+7]=1;
c[cur]=i;
search(cur+1);
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+7]=0;//注意回溯
}
return ;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
