作者seedpk5079 (fhcrc 99th ooxx)
看板C_and_CPP
標題Re: [問題] 八皇后
時間Mon Jun 22 14:47:47 2009
題目網址:
http://www.tcgs.tc.edu.tw/~sagit/luckycat/q167.htm
小弟後來找到是自己DFS的方式不對
所以我換了個做法
直接從座標(0,0)開始跑
跑到有8個皇后在stack陣列裡
就累加出答案
之後跟sum比較大小
大就取代sum反之不動
不過方法有點暴力 第一個解我就搜了快4000次...
我搜到第27組解的時候就程式就停住了
希望高手能幫我看看 感謝高手幫忙XD
===========以下為程式碼=============
/*8 queens*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int use[8][8]={},value[8][8]={},queens[8][8]={},sum=0
,solution=0,times=0,stack[8]={},top=-1;
int get_can_use(int (*map)[8],int x,int y);
void action(int (*map)[8],int coordinate,int do_now);
void DFS(int x,int y);
int pop(int *stack,int top);
int push(int *stack,int value,int top);
int get_value(int (*value_adress)[8],int total);
void put_stack();
void output(int (*map)[8],int number){
/*測試用*/
int x,y,i,k;
memset(queens,0,sizeof(queens));
printf("queens=%d\n",number);
/*queens代表目前有幾個queen再stack裡*/
for(k=0;k<=top;k++){
queens[stack[k]/10][stack[k]%10]=1;
printf("%d ",stack[k]);
}
printf("\n");
/*印出皇后圖 1為皇后位置 0等於未放置*/
for(y=0;y<8;y++){
for(x=0;x<8;x++){
printf("%d ",queens[x][y]);
}
printf("\n");
}
printf("\n");
for(y=0;y<8;y++){
for(x=0;x<8;x++){
printf("%d ",map[x][y]);
}
printf("\n");
}
/*印出實際DFS的地圖*/
printf("\n");
put_stack();
}
int main(){
int k,d;
while ( ~scanf("%d",&k)){
memset(use,0,sizeof(use));
memset(value,0,sizeof(value));
int i,j,target,u,l,replace;
for(;k>0;k--){
int total_replace=0;
/*儲存資料*/
for(i=0;i<8;i++){
for(j=0;j<8;j++){
scanf("%d",&value[j][i]);
}
}
DFS(0,0);
printf("sum=%d\n",sum);
}
}
return 0;
}
int get_can_use(int (*map)[8],int x,int y){/*抓出可放皇后的點*/
int target_x,target_y,find=0;
target_y=y;target_x=x;/*從傳入的XY座標開始找*/
for(;target_y<8&&find==0;target_y++){
for(;target_x<8;target_x++){
if(map[target_x][target_y]==0){
find=1;
/*找到即跳出*/
break;
}
}
(find==1)?:target_x=0;/*一橫行已結束 X值歸0繼續找*/
if(find==1){
break;
/*找到立即跳出 這樣才不影響Y值*/
}
}
if(find==1){
x=target_x*10+target_y;
/*target_x target_y皆為函式內宣告 傳出會有問題*/
return x;
/*target=x*10+y*/
}
else{
/*找不到點*/
return 100;
}
}
void action(int (*map)[8],int coordinate,int do_now){
/*皇后點=x*10+y 動作(do_now)=1=>放 動作(do_now)=-1=>移除*/
int start_x,start_y,method,x,y,add_number,left_up=100,left_down=100
,change,down=0,up=0;
start_x=coordinate/10;
start_y=coordinate%10;
for(x=0;x<8;x++){/*直線走法*/
map[x][start_y]+=do_now;
}
for(y=0;y<8;y++){/*橫線走法*/
map[start_x][y]+=do_now;
}
/*找斜左上跟左下的點 之後用迴圈一路跑*/
for(change=1;(down==0)||(up==0);change++){
if((((start_x-change)<0)||((start_y-change)<0))&&(up==0)){
left_up=(start_x-change+1)*10+(start_y-change+1);
up=1;
}
if(((start_x-change<0)||(start_y+change>7))&&(down==0)){
left_down=(start_x-change+1)*10+(start_y+change-1);
down=1;
}
}
/*將迴圈跳出條件歸0 重複使用*/
up=0;down=0;
for(add_number=0;(down==0)||(up==0);add_number++){/*對角線走法*/
if(((left_up/10)+add_number>7)||((left_up%10)+add_number>7)){
up=1;
}
else if(up==0){
map[(left_up/10)+add_number][(left_up%10)+add_number]+=do_now;
}
if(((left_down/10)+add_number>7)||((left_down%10)-add_number<0)){
down=1;
}
else if(down==0){
map[(left_down/10)+add_number][(left_down%10)-add_number]+=do_now;
}
}
map[start_x][start_y]+=(-1)*(do_now*3);/*皇后點重複做了了4次 把他扣回去*/
}
/*replace等於從x y開始搜尋後第一個找出可以放皇后的點
找到之後放入stack(一樣是x座標*10+y座標)
solution是計算第幾個解 times是計算DFS跑了幾次
如果找不到點 又第一個皇后位置不再第一橫行
DFS跳出(因為每一橫行皆要有皇后)
*/
void DFS(int x,int y){
int replace,replace_sum,replace_stack;
if(top==7){/*有7個皇后就累加答案*/
replace_sum=get_value(value,replace_sum);
sum=(replace_sum>sum)?replace_sum:sum;
//printf("scuess replace_sum=%d\n",replace_sum);
/*測試用*/
put_stack();
solution++;
printf("solution=%d times=%d TOP=%d\n",solution,times,top);
}
replace=get_can_use(use,x,y);
//printf("target=%d\n",replace);
if(replace==100){
times++;
if(stack[0]%10>0){
//printf("break\n");
//output(use,top);
return ;
}
replace_stack=stack[top];
action(use,stack[top],-1);
top=pop(stack,top);
replace_stack=(replace_stack/10+1)>7?replace_stack%10+1:replace_stack+10;
/*這行是要把新的DFS遞迴搜尋開始點設成後面一個點 為防止X軸加1超過8所設計*/
DFS(replace_stack/10,replace_stack%10);
}
else{
times++;
action(use,replace,1);
top=push(stack,replace,top);
DFS(replace/10,replace%10);
}
}
int get_value(int (*value_adress)[8],int total){/*get sum from stack*/
/*get value from stack*/
int number,i,j;
total=0;/*這裡不歸0會怪怪的*/
for(number=0;number<8;number++){
total+=value_adress[stack[number]/10][stack[number]%10];
queens[stack[number]/10][stack[number]%10]=1;
}/*不一邊存資料一邊將stack移出是因為還要繼續使用*/
return total;
}
int pop(int *stack,int top){
if(top==-1){
return -1;
}
else{
stack[top]=0;
top--;
return top;
}
}
int push(int *stack,int value,int top){
if(top==7){
return 8;
}
else{
top++;
stack[top]=value;
return top;
}
}
void put_stack(){/*印出stack目前有的資料*/
int i;
printf("#");
for(i=0;i<=top;i++){
printf("%d ",stack[i]/10);
}
printf("\n\n");
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.60.161.254
※ 編輯: seedpk5079 來自: 210.60.161.254 (06/22 14:49)
※ 編輯: seedpk5079 來自: 210.60.161.254 (06/22 14:51)