POJ ~ 3984 ~ 迷宫问题 (BFS+打印路径)

xiaoxiao2021-02-28  12

题意:输入一个5*5的迷宫地图,输出一条最短路径。

思路:BFS+路径输出。裸的路径输出问题。开一个存路径的结构体,每个点存来的点的坐标,然后递归到起点,回溯输出路径。

//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<queue> using namespace std; int n, m, MAP[15][15], dir[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}}; bool vis[15][15]; pair<int, int> path[15][15], NOW; void bfs() { queue<pair<int, int> > q; q.push(make_pair(0, 0)); while (!q.empty()) { NOW = q.front(); q.pop(); if (NOW.first == 4 && NOW.second == 4) return ; for (int i = 0; i < 4; i++) { int X = NOW.first + dir[i][0], Y = NOW.second + dir[i][1]; if (X >= 0 && Y >= 0 && X < n && Y < m && MAP[X][Y] == 0 && !vis[X][Y]) { q.push(make_pair(X, Y)); path[X][Y].first = NOW.first, path[X][Y].second = NOW.second; } } } } void putout(int x, int y) { if (x == 0 && y ==0) { printf("(0, 0)\n"); return ; } putout(path[x][y].first, path[x][y].second); printf("(%d, %d)\n",x ,y); } int main() { n = 5; m = 5; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d",&MAP[i][j]); } } bfs(); putout(4, 4); return 0; } /* 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 */

转载请注明原文地址: https://www.6miu.com/read-250411.html

最新回复(0)