A*搜索 实际上只有空格再走

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #define rep(i,l,r) for(int i=l;i
             
              ans) return 0;34 return 1;35 }36 int cnt=0;37 void dfs(int x,int y,int d)38 { 39 if(d==ans&&same()){40 flag=1;41 return;42 }43 if(flag) return;44 rep(i,0,8){45 int x1=x+dir[i][0],y1=y+dir[i][1];46 if(legal(x1,y1)){47 swap(now[x][y],now[x1][y1]);48 if(estimate(d)) dfs(x1,y1,d+1);49 swap(now[x][y],now[x1][y1]);50 }51 }52 }53 int main()54 { 55 int t;56 cin>>t;57 while(t--){58 clr(now,0);59 int x,y;60 flag=0;61 rep(i,0,n) 62 rep(j,0,n){63 char c=getchar();64 while(c!='*'&&!isdigit(c)) c=getchar();65 if(c=='*') now[x=i][y=j]=2;66 else now[i][j]=c-'0';67 }68 for(ans=1;ans<=15;ans++){69 dfs(x,y,0);70 if(flag) break;71 }72 printf("%d\n",flag?ans:-1);73 }74 return 0;75 }
             
            
           
          
         
        
       
      

1085: [SCOI2005]骑士精神

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 1110  Solved: 602

[][][]

Description

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。

Input

第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。

Output

对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

Sample Input

2

10110

01*11

10111

01001

00000

01011

110*1

01110

01010

00100

Sample Output

7

-1

HINT

 

Source

 

[ ][ ][ ]