hdu1372 Knight Moves BFS 搜索

简单BFS题目主要是读懂题意

和中国的象棋中马的走法一样，走日字型，共八个方向

我最初wa在初始化上了。。。。以后多注意。。。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include<cstdlib>
 4 #include <cstring>
 5 #include<queue>
 6 using namespace std; 
 7 char a[5],b[5];
 8 int map[9][9];
 9 int end_x,end_y;
10 int d[8][2]={{-2,1},{-2,-1},{2,1},{2,-1},{-1,2},{-1,-2},{1,2},{1,-2}};
11 class node
12 {
13         public:
14         int x;
15         int y;
16         int step;
17         friend bool operator <(node a,node b)
18         {
19                 return a.step>b.step;
20         }
21 }cur,next;
22 priority_queue<node> q;
23 void init()
24 {
25         for(int i=0;i<9;i++)
26                 for(int j=0;j<9;j++)
27                         map[i][j]=1;
28 }
29 void bfs()
30 {
31        while(!q.empty())
32        {
33                cur=q.top();
34                q.pop();
35                if(cur.x==end_x&&cur.y==end_y)
36                {
37                        printf("To get from %s to %s takes %d knight moves.
", a,b,cur.step);
38                        return ;
39                }
40                for(int i=0;i<8;i++)
41                {
42                        int x=cur.x+d[i][0];
43                        int y=cur.y+d[i][1];
44                        if(x>8||x<1||y>8||y<1||map[x][y]==0)  continue;
45                        next.x=x;
46                        next.y=y;
47                        map[x][y]=0;
48                        next.step=cur.step+1;
49                        q.push(next);
50                }
51        }
52 }
53 int main()
54 {
55     while(scanf("%s %s",a,b)!=EOF)
56       {
57         init();
58         while(!q.empty()) q.pop();
59         int y1=a[0]-'a'+1;
60         int x1=a[1]-'0';
61         int y2=b[0]-'a'+1;
62         int x2=b[1]-'0';
63         cur.x=x1;
64         cur.y=y1;
65         cur.step=0;
66         q.push(cur);
67         end_x=x2;
68         end_y=y2;
69         bfs();
70       }
71       return 0;
72 }

View Code