Re: [問題] 八皇后

看板C_and_CPP (C/C++)作者seedpk5079 (fhcrc 99th ooxx)時間16年前 (2009/06/22 14:47)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

題目網址: 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)