摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法: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;
}