华为2017机试模拟 迷宫问题

云中漫步

　　题目：

题目描述：　　sun所在学校每年都要举行电脑节，今年电脑节有一个新的趣味比赛项目叫做闯迷宫。
sun的室友在帮电脑节设计迷宫，所以室友就请sun帮忙计算下走出迷宫的最少步数。
知道了最少步数就可以辅助控制比赛难度以及去掉一些没有路径到达终点的map。
比赛规则是：从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走。

输入：　　输入有多组数据。
每组数据输入n（0<n<=100），然后输入n*n的01矩阵，0代表该格子没有障碍，为1表示有障碍物。
注意：如果输入中的原点和终点为1则这个迷宫是不可达的。

输出：　　对每组输入输出该迷宫的最短步数，若不能到达则输出-1。

样例输入：
2
0 1
0 0
5
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
0 1 1 1 0
1 0 1 0 0
样例输出：
2
8
　　思路：
　　解决迷宫类似问题，如果是能不能到达，一般选用的是dfs，如果是求最短步数，一般选用的是bfs。
基本思路：

　　本题要求的是最短步数，所以可以选用bfs。
       1、输入数据存储至结构体；
       2、从开始节点开始依次访问，发现到出口了，就return，否则继续，直到循环结束。
       3、比较打印结果。
　　代码：



1 #include <vector>
2 #include <queue>
3 #include <iostream>
4 #include <algorithm>
5 using namespace std;
6
7
8
9 int mat[100][100];
10 int flag[100][100];
11 int stepArr[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
12
13 struct Node
14 {
15     int x;
16     int y;
17     int step;
18     Node(int x1, int y1, int s1) :x(x1), y(y1), step(s1) {}
19 };
20
21 int bfs(int n)
22 {
23     Node node(0, 0, 0);
24     queue<Node> que;
25     que.push(node);
26     while (!que.empty())
27     {
28         node = que.front();
29         que.pop();
30         if (node.x == n - 1 && node.y == n - 1)
31             return node.step;
32         flag[node.x][node.y] == 1;
33         for (int i = 0; i < 4; ++i)
34         {
35             int x = node.x + stepArr[0];
36             int y = node.y + stepArr[1];
37             if (x >= 0 && y >= 0 && x < n && y < n
38                 && flag[x][y] == 0 && mat[x][y] == 0)
39             {
40                 flag[x][y] = 1;
41                 Node next(x, y, node.step + 1);
42                 que.push(next);
43             }
44         }
45     }
46     return -1;
47 }
48
49 int main()
50 {
51     int n;
52     while (cin >> n)
53     {
54         for(int i = 0; i < n; ++i)
55             for (int j = 0; j < n; ++j)
56             {
57                 cin >> mat[j];
58                 flag[j] = 0;
59             }
60         int depth = 0;
61         cout << bfs(n) << endl;
62     }
63 }