POJ 2243 Knight Moves

BFS模板题
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <queue>
 5 using namespace std;
 6 char pos_start[3],pos_end[3];
 7 bool visited[20][20]={false};
 8 int dis[20][20]={0};
 9 typedef struct Node {
10     int x,y;
11 }Node;
12 Node nodes[8]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
13 void init()
14 {
15     memset(visited,false,sizeof(visited));
16     int i,j;
17     for(i=0;i<20;i++) 
18         for(j=0;j<20;j++)
19             dis[i][j]=0;
20 }
21 bool check(int x,int y)
22 {
23     if(!(1<=x&&x<=8&&0<=y&&y<=7))    return false;
24     return true;
25 }
26 int bfs(int s_x,int s_y,int e_x,int e_y)
27 {
28     queue<int> Q;
29     Q.push(s_x);
30     Q.push(s_y);
31     dis[s_x][s_y]=0;
32     while(!Q.empty()) {
33         int x=Q.front();
34         Q.pop();
35         int y=Q.front();
36         Q.pop();
37         if(x==e_x&&y==e_y)    return dis[x][y];
38         visited[x][y]=true;
39         int i;
40         for(i=0;i<8;i++) {
41             if(check(x+nodes[i].x,y+nodes[i].y)&&!visited[x+nodes[i].x][y+nodes[i].y]) {
42                 Q.push(x+nodes[i].x);
43                 Q.push(y+nodes[i].y);
44                 dis[x+nodes[i].x][y+nodes[i].y]=dis[x][y]+1;
45             }
46         }
47     }        
48 }
49 
50 int main()
51 {
52     while(scanf("%s%s",pos_start,pos_end)!=EOF) {
53         int start_x=pos_start[1]-'0';
54         int start_y=pos_start[0]-'a';
55         int end_x=pos_end[1]-'0';
56         int end_y=pos_end[0]-'a';
57         int moves=bfs(start_x,start_y,end_x,end_y);
58         init();
59         printf("To get from %s to %s takes %d knight moves.\n",pos_start,pos_end,moves);
60     }
61     return 0;
62 }