首页 > 代码库 > poj 1915 BFS

poj 1915 BFS

2024-07-03 16:25:55   230人阅读

 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 }
View Code

 


联系
我们