数据结构实习 Problem H 迷宫的最短路径
题目描述
设计一个算法找一条从迷宫入口到出口的最短路径。
输入
迷宫的行和列m n
迷宫的布局
输出
最短路径
样例输入
6 8
0 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0
0 1 0 0 1 1 1 1
0 1 1 1 0 0 1 1
1 0 0 1 1 0 0 0
0 1 1 0 0 1 1 0
样例输出
（6,8）
（5,7）
（4,6）
（4,5）
（3,4）
（3,3）
（2,2）
（1,1）
代码如下：
#include#include #include #include #include using namespace std;const int maxn = 1000;int dx[] = {1,1,0,-1,-1,-1,0,1};int dy[] = {0,-1,-1,-1,0,1,1,1};int n, m;int ** maze;int ** vis;struct node{ int x, y; node(int a, int b):x(a),y(b){} node():x(0),y(0){}};node pre[maxn][maxn];queue qu;vector a;void BFS(){ node cur; while(!qu.empty())qu.pop(); int c,r; //记录路径 cur.x = 1,cur.y = 1; qu.push(cur); vis[1][1] = 1; while(!qu.empty()) { cur = qu.front(); qu.pop(); //判断是否已经达到终点 if(cur.x == n && cur.y == m) { a.push_back(node(n,m)); while(cur.x != 1||cur.y != 1) { r = cur.x; c = cur.y; a.push_back(node(pre[r][c].x,pre[r][c].y)); cur.x = pre[r][c].x,cur.y = pre[r][c].y; } for(int i = 0 ; i < a.size()-1; i++) printf("(%d,%d)\n", a[i].x, a[i].y); return ; } for(int i = 0 ; i < 8; i++) { //方向调整 r = cur.x + dx[i]; c = cur.y + dy[i]; if(r >= 1 && r <= n && c >= 1 && c <= m && vis[r][c] == 0 && maze[r][c] == 0) { vis[r][c] = vis[cur.x][cur.y]+1; pre[r][c] = node(cur.x,cur.y); qu.push(node(r,c)); } } }}void print(){ for(int i = 0; i < n + 2; i++) { for(int j = 0 ; j < m + 2; j++) { cout << maze[i][j] << " "; } cout << endl; } cout << endl; for(int i = 0 ; i < n+2; i++) { for(int j = 0 ; j < m+2; j++) { cout << vis[i][j] << " "; } cout << endl; } return;}int main(){ freopen("in.txt","r",stdin); cin >> n >> m; maze = new int* [n+2]; vis = new int* [n+2]; for(int i = 0 ; i < n + 2; i++) { maze[i] = new int[m+2]; vis[i] = new int[m+2]; } for(int i = 0 ; i < n+2; i++) for(int j = 0 ; j < m+2; j++) { maze[i][j] = 1; vis[i][j] = 1; } for(int i = 1; i <= n ; i++) for(int j = 1; j <= m ; j++) { cin >> maze[i][j]; vis[i][j] = 0; } BFS(); cout << "(1,1)" << endl; return 0;}