[問題] 八皇后

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

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

小弟最近在做八皇后題目網址: http://www.tcgs.tc.edu.tw/~sagit/luckycat/q167.htm 往上有很多做法但我看不大懂所以我就直覺直接用DFS爆搜它就是用迴圈跑過64個點每個點都讓它做為第一個皇后的位置註:action的函式我試過應該沒問題用途就是一個點放入後依皇后規則將攻擊範圍全加上1 題目給的兩個測資試過了可是我傳上去時出現這行與正確輸出不相符(line:2) 您的答案為: 636 正確答案為: 663 希望有解過的高手能幫忙看看 =================以下是程式碼================== /*8 queens*/ #include<stdio.h> #include<string.h> #include<deque> using namespace std; deque<int> stack; int use[8][8]={},value[8][8]={},test=40; int get_can_use(int (*map)[8],int x,int y); void action(int (*map)[8],int coordinate,int do_now); int DFS(int x,int y,int queens_amount); int get_value(int (*value_adress)[8],int total); void output(int (*map)[8]){ /*just for test*/ int x,y; for(y=0;y<8;y++){ for(x=0;x<8;x++){ printf("%d ",map[x][y]); } printf("\n"); } printf("\n"); } 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 sum=0,total_replace=0; /*save value*/ for(i=0;i<8;i++){ for(j=0;j<8;j++){ scanf("%d",&value[j][i]); } } /*DFS*/ for(u=0;u<8;u++){ for(l=0;l<8;l++){ total_replace=0; action(use,l*10+u,1); stack.push_back(l*10+u); /*set first queen*/ replace=DFS(0,0,1); if(replace==0){ /*start new point*/ memset(use,0,sizeof(use)); continue; } else if(replace==1){ memset(use,0,sizeof(use)); total_replace=get_value(value,total_replace); /*just for test*/ //printf("total_replace=%d\n",total_replace); stack.clear(); /*find max*/ sum=(sum>total_replace)?sum:total_replace; } } } printf("%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; 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; if(find==1){ break; } } if(find==1){ x=target_x*10+target_y; /*just for test*/ //printf("----%d\n",x); return x; /*target=x*10+y*/ } else{ /*can't find point*/ return 100; } } void action(int (*map)[8],int coordinate,int do_now){ /*coordinate=x*10+y do_now=1=>put do_now=-1=>remove*/ 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++){/*straight walk*/ map[x][start_y]+=do_now; } for(y=0;y<8;y++){/*parallel walk*/ map[start_x][y]+=do_now; } /*find the start point of oblique walk*/ 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++){/*oblique walk*/ 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);/*start repart action 3 times*/ } int DFS(int x,int y,int queens_amount){ int queen,next; if(queens_amount==7){ /*set completely=>break*/ //output(use); return 1; } else { queen=get_can_use(use,x,y); if(queen>=100){ if(stack.size()-1==0){ stack.clear(); if(test>=0){ //output(use); test--; } return 0; } else{ next=stack[stack.size()-1]; /*從失敗的點往後找*/ action(use,stack[stack.size()-1],-1); stack.pop_back(); if(test>=0){ /*just for test*/ //output(use); test--; } if((next/10)+1<=7){ /*往後找一點不要再用失敗的點*/ return DFS(next/10+1,next%10,stack.size()-1); } else { /*往後找一個時超過了邊界*/ return DFS(0,next%10+1,stack.size()-1); } } } else{ action(use,queen,1); stack.push_back(queen); if(test>=0){ //output(use); test--; } return DFS(queen/10,queen%10,stack.size()-1); /*find next one*/ } } } int get_value(int (*value_adress)[8],int total){/*get sum from stack*/ /*get value from stack*/ int number; for(number=0;number<8;number++){ total+=value_adress[stack[stack.size()-1]/10][stack[stack.size()-1]%10]; printf("%d ",stack[stack.size()-1]); stack.pop_back(); } printf("\n"); return total; } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.143.159.1 ※ 編輯: seedpk5079 來自: 220.143.159.1 (06/10 22:35) ※ 編輯: seedpk5079 來自: 220.143.159.1 (06/10 22:42)