2007 NPSC H. 數字拼盤
作法:DFS搜尋所有可能
想法:紀錄上一次的動作,以免走回去
8-PUZZLE問題
/**********************************************************/
#include<stdio.h>
#include<stdlib.h>
int map[7][7]={0};
int startx,starty,find;
void DFS(int nowx,int nowy,int time,int last)
{
if(find==1||time>20) return;
int a,b,num=1,same=0;
for(a=1;a<=3;a++)
for(b=1;b<=3;b++,num++)
if(map[a][b]==num) same++;
if(same==8) {find=1;}
/*last 1上 2 右 3 下 4 左 */
a=nowx;b=nowy;
if(map[a][b-1]!=-1&&last!=2)
{
/*printf("左\n"); */
int temp=map[a][b],temp1=map[a][b-1];
map[a][b]=temp1;
map[a][b-1]=temp;
DFS(a,b-1,time+1,4);
map[a][b]=temp;
map[a][b-1]=temp1;
}
if(map[a][b+1]!=-1&&last!=4)
{
/* printf("右\n"); */
int temp=map[a][b],temp1=map[a][b+1];
map[a][b]=temp1;
map[a][b+1]=temp;
DFS(a,b+1,time+1,2);
map[a][b]=temp;
map[a][b+1]=temp1;
}
if(map[a-1][b]!=-1&&last!=1)
{
/* printf("上\n"); */
int temp=map[a][b],temp1=map[a-1][b];
map[a][b]=temp1;
map[a-1][b]=temp;
DFS(a-1,b,time+1,3);
map[a][b]=temp;
map[a-1][b]=temp1;
}
if(map[a+1][b]!=-1&&last!=3)
{
/* printf("下\n"); */
int temp=map[a][b],temp1=map[a+1][b];
map[a][b]=temp1;
map[a+1][b]=temp;
DFS(a+1,b,time+1,1);
map[a][b]=temp;
map[a+1][b]=temp1;
}
}
main()
{
int n,a,b,c;
for(a=0;a<7;a++)
for(b=0;b<7;b++)
map[a][b]=-1;
scanf("%d",&n);
while(n--)
{
for(a=1;a<=3;a++)
for(b=1;b<=3;b++)
{
scanf("%d",&map[a][b]);
if(map[a][b]==0)
{startx=a;starty=b;}
}
find=0;
DFS(startx,starty,0,0);
if(find==0) printf("Hard\n");
else printf("Easy\n");
}
return 0;
}
上一篇:2006 NPSC D. 水之都