1 /* 2 题意：国际象棋起点到终点移动的最少步数 3 4 题解：水题，BFS就过了，有人用双向BFS 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <queue> 9 10 using namespace std; 11 12 int dir[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1}; 13 14 bool gra[305][305]; 15 16 struct node 17 { 18 int x,y,step; 19 bool operator==(const node & t)const 20 { 21 if (x == t.x && y == t.y) 22 return true; 23 else 24 return false; 25 } 26 }Q[90005]; 27 int front,tail; 28 int bfs(int l, node start, node end) 29 { 30 front = tail = 0; 31 Q[tail++] = start; 32 gra[start.x][start.y] = true; 33 while (front < tail) 34 { 35 node now = Q[front++]; 36 if (now == end) 37 return now.step; 38 for(int i=0; i<8; i++) 39 { 40 int nx = now.x + dir[i][0]; 41 int ny = now.y + dir[i][1]; 42 if (0 <= nx && nx < l && 0 <= ny && ny < l && !gra[nx][ny]) 43 { 44 node tmp = now; 45 tmp.step = now.step + 1; 46 tmp.x = nx; 47 tmp.y = ny; 48 Q[tail++] = tmp; 49 gra[nx][ny] = true; 50 } 51 } 52 } 53 } 54 55 int main(void) 56 { 57 int t; 58 scanf("%d",&t); 59 while (t--) 60 { 61 int l; 62 scanf("%d",&l); 63 node start; 64 node end; 65 scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y); 66 start.step = 0; 67 memset(gra,false,sizeof(gra)); 68 printf("%d\n",bfs(l,start,end)); 69 } 70 return 0; 71 }
双向BFS实现：
1 /* 2 题意：国际象棋起点到终点移动的最少步数 3 4 题解：参考网上其它人的代码写了个双向bfs，也许这个双向用得不太好，没快多少 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <queue> 9 10 #define FOR 2 11 #define BACK 3 12 13 using namespace std; 14 15 int dir[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1}; 16 17 int gra[305][305]; 18 int steps[305][305]; 19 20 struct node 21 { 22 int x,y; 23 bool operator==(const node & t)const 24 { 25 if (x == t.x && y == t.y) 26 return true; 27 else 28 return false; 29 } 30 }fQ[45005],bQ[45005]; 31 int ffront,ftail,bfront,btail; 32 int bi_bfs(int l, node start, node end) 33 { 34 if (start == end) 35 return 0; 36 ffront = ftail = bfront = btail = 0; 37 fQ[ftail++] = start; 38 bQ[btail++] = end; 39 gra[start.x][start.y] = FOR; 40 gra[end.x][end.y] = BACK; 41 while (ffront < ftail && bfront < btail) 42 { 43 if (ftail - ffront <= btail - bfront) 44 { 45 node now = fQ[ffront++]; 46 for(int i=0; i<8; i++) 47 { 48 int nx = now.x + dir[i][0]; 49 int ny = now.y + dir[i][1]; 50 if (0 <= nx && nx < l && 0 <= ny && ny < l) 51 { 52 if (!gra[nx][ny]) 53 { 54 node tmp; 55 tmp.x = nx; 56 tmp.y = ny; 57 steps[nx][ny] = steps[now.x][now.y] + 1; 58 fQ[ftail++] = tmp; 59 gra[nx][ny] = FOR; 60 } 61 else if (gra[nx][ny] == BACK) 62 return steps[nx][ny] + steps[now.x][now.y] + 1; 63 } 64 } 65 } 66 else 67 { 68 node now = bQ[bfront++]; 69 for(int i=0; i<8; i++) 70 { 71 int nx = now.x + dir[i][0]; 72 int ny = now.y + dir[i][1]; 73 if (0 <= nx && nx < l && 0 <= ny && ny < l) 74 { 75 if (!gra[nx][ny]) 76 { 77 node tmp; 78 tmp.x = nx; 79 tmp.y = ny; 80 steps[nx][ny] = steps[now.x][now.y] + 1; 81 bQ[btail++] = tmp; 82 gra[nx][ny] = BACK; 83 } 84 else if (gra[nx][ny] == FOR) 85 return steps[nx][ny] + steps[now.x][now.y] + 1; 86 } 87 } 88 } 89 } 90 } 91 92 int main(void) 93 { 94 int t; 95 scanf("%d",&t); 96 while (t--) 97 { 98 int l; 99 scanf("%d",&l); 100 node start; 101 node end; 102 scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y); 103 memset(steps,0,sizeof(steps)); 104 memset(gra,0,sizeof(gra)); 105 printf("%d\n",bi_bfs(l,start,end)); 106 } 107 return 0; 108 }
原文：http://www.cnblogs.com/toufu/p/3716944.html
