作者seedpk5079 (fhcrc 99th ooxx)
看板C_and_CPP
標題[問題] 八皇后
時間Wed Jun 10 22:32:24 2009
小弟最近在做八皇后
題目網址:
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)
1F：推 johnlinvc:一般來說8Queen都是用recursive吧 06/10 23:16
2F：→ netsphere:要不然你也可以放大絕 直接寫八個迴圈 ~ 06/10 23:29
3F：→ sosokill:推樓上 我當初就是放大決XD 06/10 23:30
4F：→ seedpk5079:我這個其實跟放大絕沒啥兩樣 迴圈看起來比較少而已... 06/11 12:38