题目:
定义一个二维数组:
- int maze[5][5] = {
- 0, 1, 0, 0, 0,
- 0, 1, 0, 1, 0,
- 0, 0, 0, 0, 0,
- 0, 1, 1, 1, 0,
- 0, 0, 0, 1, 0,
- };
它表示一个迷宫, 其中的 1 表示墙壁, 0 表示可以走的路, 只能横着走或竖着走, 不能斜着走, 要求编程序找出从左上角到右下角的最短路线.
输入:
一个 5 * 5 的二维数组, 表示一个迷宫. 数据保证有唯一解.
输出:
左上角到右下角的最短路径, 格式如样例所示.
样例:
分析: BFS 回溯, 套路固定, 定义结构体储存点和路径
- #include<iostream>
- #include<sstream>
- #include<cstdio>
- #include<cstdlib>
- #include<string>
- #include<cstring>
- #include<algorithm>
- #include<functional>
- #include<iomanip>
- #include<numeric>
- #include<cmath>
- #include<queue>
- #include<vector>
- #include<set>
- #include<cctype>
- #define PI acos(-1.0)
- const int INF = 0x3f3f3f3f;
- const int NINF = -INF - 1;
- typedef long long ll;
- using namespace std;
- typedef pair<int, int> P;
- int maze[5][5];
- int used[5][5];
- int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
- struct node
- {
- int x, y;
- int flag;
- P path[30];
- };
- void bfs()
- {
- queue<node> q;
- memset(used, 0, sizeof(used));
- node st;
- st.x = 0, st.y = 0, st.flag = 0;
- st.path[st.flag] = P(0, 0);
- q.push(st);
- used[st.x][st.y] = 1;
- while (q.size())
- {
- node temp = q.front();
- q.pop();
- if (temp.x == 4 && temp.y == 4)
- {
- for (int i = 0; i <= temp.flag; ++i)
- cout <<'(' << temp.path[i].first << "," << temp.path[i].second << ')' << endl;
- return;
- }
- for (int i = 0; i < 4; ++i)
- {
- node n = temp;
- n.flag++;
- n.x = temp.x + dx[i], n.y = temp.y + dy[i];
- if (n.x>= 0 && n.x <5 && n.y>= 0 && n.y <5 && !used[n.x][n.y] && maze[n.x][n.y] == 0)
- {
- used[n.x][n.y] = 1;
- n.path[n.flag] = P(n.x, n.y);
- q.push(n);
- }
- }
- }
- }
- int main()
- {
- for (int i = 0; i < 5; ++i)
- {
- for (int j = 0; j < 5; ++j)
- cin>> maze[i][j];
- }
- bfs();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3085669.html