迷宫问题

题目描述

定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。 Input 一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。 Output 左上角到右下角的最短路径，格式如样例所示。 Sample Input 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 Sample Output (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)

输入描述: 输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述: 左上角到右下角的最短路径，格式如样例所示。

输入例子: 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

输出例子: (0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)

算法思想

广度优先遍历

代码块

#include <iostream> #include <vector> #include <queue> using namespace std; struct point //坐标 { int x; int y; }; vector<point> direct = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } }; //方向 上下左右 // bool isOk(vector<vector<int>> &vec, point p, point direct,int m, int n, int ok) { if ((p.x + direct.x >= 0 && p.x + direct.x < n) && (p.y + direct.y >= 0 && p.y + direct.y < m) && vec[p.y + direct.y][p.x + direct.x] == ok) { return true; } else { return false; } } //广度优先遍历 void BFS(vector<vector<int>> &vec,int m,int n) { point p = { 0, 0 },temp; vec[0][0] = 2; queue<point> Q; Q.push(p); bool flag = false; while (!Q.empty()) { p = Q.front(); Q.pop(); for (int i = 0; i < 4; ++i) { if (isOk(vec, p, direct[i], m, n, 0)) { vec[p.y + direct[i].y][p.x + direct[i].x] = vec[p.y][p.x] + 1; if (p.x + direct[i].x == n - 1 && p.y + direct[i].y == m - 1) { flag = true; break; } temp.x = p.x + direct[i].x; temp.y = p.y + direct[i].y; Q.push(temp); } } if (flag) break; } p.x = n - 1; p.y = m - 1; vector<point> vp; vp.push_back(p); while (!(p.x == 0 && p.y == 0)) { for (int i = 0; i < 4; ++i) { if (isOk(vec, p, direct[i], m, n, vec[p.y][p.x] - 1)) { p.x += direct[i].x; p.y += direct[i].y; vp.push_back(p); break; } } } for (int i = vp.size()-1; i >=0; --i) { cout << '(' << vp[i].y << ',' << vp[i].x << ')' << endl; } vp.clear(); } int main() { int m, n; while (cin >> m >> n) { vector<vector<int>> vec(m, vector<int>(n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { cin >> vec[i][j]; } } BFS(vec, m, n); vec.clear(); } }