nyoj 58-最少步数 (BFS)

58-最少步数

内存限制:64MB 时间限制:3000ms Special Judge: No
accepted:17 submit:22

题目描述:

这有一个迷宫，有0~8行和0~8列：

1,1,1,1,1,1,1,1,1
1,0,0,1,0,0,1,0,1
1,0,0,1,1,0,0,0,1
1,0,1,0,1,1,0,1,1
1,0,0,0,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,0,0,0,1
1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入描述:

第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出描述:

输出最少走几步。

样例输入:

2
3 1  5 7
3 1  6 7

样例输出:

12
11

分析：
　　1、BFS模板题

核心代码（模板）：

 1 int bfs()
 2 {
 3     queue <node> Q;
 4     node q1, q2;
 5     q1.x = a, q1.y = b, q1.step = 0;
 6     my_book[a][b] = 1;
 7     Q.push(q1);
 8     while(!Q.empty())
 9     {
10         q1 = Q.front();
11         if(q1.x == c && q1.y == d) return q1.step;
12         for(int i = 0; i <= 3; ++ i)
13         {
14             q2 = q1;
15             q2.x = q1.x + mov[i][0];
16             q2.y = q1.y + mov[i][1];
17             q2.step = q1.step + 1;
18             if(match(q2))
19             {
20                 my_book[q2.x][q2.y] = 1;
21                 Q.push(q2);
22             }
23         }
24         Q.pop();
25     }
26 }

C/C++代码实现（AC）：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <stack>
 7 #include <map>
 8 #include <queue>
 9 #include <set>
10 
11 using namespace std;
12 const int MAXN = 12;
13 const int A[9][9] = {1,1,1,1,1,1,1,1,1,
14                      1,0,0,1,0,0,1,0,1,
15                      1,0,0,1,1,0,0,0,1,
16                      1,0,1,0,1,1,0,1,1,
17                      1,0,0,0,0,1,0,0,1,
18                      1,1,0,1,0,1,0,0,1,
19                      1,1,0,1,0,1,0,0,1,
20                      1,1,0,1,0,0,0,0,1,
21                      1,1,1,1,1,1,1,1,1};
22 int a, b, c, d, cnt, mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, my_book[MAXN][MAXN];
23 struct node
24 {
25     int x, y, step;
26 };
27 
28 bool match(node q)
29 {
30     if (q.x < 0 || q.y < 0 || q.x > 8 || q.y > 8) return false;
31     if (my_book[q.x][q.y]) return false;
32     if (A[q.x][q.y]) return false;
33     return true;
34 }
35 
36 int bfs()
37 {
38     queue <node> Q;
39     node q1, q2;
40     q1.x = a, q1.y = b, q1.step = 0;
41     my_book[a][b] = 1;
42     Q.push(q1);
43     while(!Q.empty())
44     {
45         q1 = Q.front();
46         if(q1.x == c && q1.y == d) return q1.step;
47         for(int i = 0; i <= 3; ++ i)
48         {
49             q2 = q1;
50             q2.x = q1.x + mov[i][0];
51             q2.y = q1.y + mov[i][1];
52             q2.step = q1.step + 1;
53             if(match(q2))
54             {
55                 my_book[q2.x][q2.y] = 1;
56                 Q.push(q2);
57             }
58         }
59         Q.pop();
60     }
61 }
62 
63 int main()
64 {
65     int t;
66     scanf("%d", &t);
67     while(t --)
68     {
69         memset(my_book, 0, sizeof(my_book));
70         scanf("%d%d%d%d", &a, &b, &c, &d);
71         printf("%d
",bfs());
72     }
73     return 0;
74 }