The Sultan's Successors UVA 167(八皇后問題)
來源:程序員人生 發(fā)布時間:2014-10-06 08:00:01 閱讀次數(shù):3277次
說說:
其實這道題本質(zhì)上就是一個八皇后問題。唯一的區(qū)別就是每個棋盤的格子都對應(yīng)一個數(shù)字。最后要求輸出,對應(yīng)的解占據(jù)的格子的和的最大值。這只要在最后求出解的時候統(tǒng)計一下就可以了。下面就簡單的說說八皇后問題,其實解法也不難。因為要求每行每列都要有棋子。因此只要確定每一行對應(yīng)的棋子的列數(shù)就可以了。而對于每個棋子的所放的位置,同列上和對角線上不能有其他棋子,這個只要設(shè)一個訪問數(shù)組保存一下就可以了。(注意要記得回溯)。至于對角線的表示方法,例如所在位置為(x,y),那么一條對角線可以用x+y表示,另一條對角線可以用x-y表示,但是由于數(shù)組的下標(biāo)非負(fù),因此可以將第二條對角線的值設(shè)為x-y+7,這樣就可以用一個二維數(shù)組來表示,一個相應(yīng)的位置上能不能放棋子啦。具體的分析,請參見劉汝佳的《算法競賽入門經(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)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進(jìn)行捐贈