HDU１３７２

模板

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 int step; 7 int to[8][2] = {-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};//骑士移动的8个方位 8 int map[10][10],ex,ey; 9 char s1[5],s2[5];10 11 struct node12 {13     int x,y,step;14 };15 16 int check(int x,int y)17 {18     if(x<0 || y<0 || x>=8 || y>=8 || map[x][y])19     return 1;20     return 0;21 }22 23 int bfs()24 {25     int i;26     queue
        
          Q;27     node p,next,q;28     p.x = s1[0]-'a';29     p.y = s1[1]-'1';30     p.step = 0;31     ex = s2[0]-'a';32     ey = s2[1]-'1';33     memset(map,0,sizeof(map));34     map[p.x][p.y] = 1; 35     Q.push(p);36     while(!Q.empty())37     {38         q = Q.front();39         Q.pop();40         if(q.x == ex && q.y == ey)41         return q.step;42         for(i = 0;i<8;i++)43         {44             next.x = q.x+to[i][0];45             next.y = q.y+to[i][1];46             if(next.x == ex && next.y == ey)47             return q.step+1;48             if(check(next.x,next.y))49             continue;50             next.step = q.step+1;51             map[next.x][next.y] = 1;52             Q.push(next);53         }54     }55     return 0;56 }57 58 int main()59 {60     while(~scanf("%s%s",s1,s2))61     {62         printf("To get from %s to %s takes %d knight moves.\n",s1,s2,bfs());63     }64     return 0;65 }