本文主要是介绍迷宫问题~写题笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
定义一个二维数组：
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
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)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<cstdio>
using namespace std;
int Map[10][10];
int Min = 99999;
int vis[10][10];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
struct node
{int x, y;}a,tmp[100];
stack<node> s;
int m = 0;
void dfs(int x, int y, int step)
{//cout << "x=" << x << " " << "y=" << y << endl; if(x == 4 && y == 4){ if(step < Min) {m = 0;Min = step ;while(!s.empty()){tmp[m++] = s.top();// cout << s.top().x << " " << s.top().y << endl;s.pop();}for(int i = m-1; i >= 0; i--){s.push(tmp[i]);} return ;}}for(int i = 0; i < 4; i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if(!vis[nx][ny] && Map[nx][ny] == 0 && nx >= 0 && nx <= 4 && ny >= 0 && ny <= 4){ a.x = nx, a.y = ny;s.push(a);vis[nx][ny] = 1;dfs(nx, ny, step+1);s.pop();vis[nx][ny] = 0;}}}
int main()
{for(int i = 0; i <= 4; i++){for(int j = 0; j < 5; j++){cin >> Map[i][j]; } }vis[0][0] = 1;dfs(0,0,0) ;
// cout << Min << endl;printf("(0, 0)\n");for(int i = Min - 1; i >= 0; i--) cout << "(" << tmp[i].x << ", " << tmp[i].y << ")"<< endl;return 0;}以下bfs只求出步数
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct node
{int x, y;int step;node(){}node(int _x, int _y, int _step) : x(_x),y(_y),step(_step) {} //构造函数
};
int Map[10][10];
//int Min = 9999;
int vis[10][10];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int bfs()
{queue<node> q;q.push(node(0,0, 0));memset(vis, 0, sizeof(vis));vis[0][0] = 1;int flag = 0;while(!q.empty()){struct node now;now = q.front();if(now.x == 4 && now.y == 4) {return now.step; }q.pop();vis[now.x][now.y] = 0;for(int i = 0; i < 4; i++){struct node next;next.x = now.x + dir[i][0];next.y = now.y + dir[i][1];next.step = now.step + 1;if(!vis[next.x][next.y] && next.x >= 0 && next.x < 5 && next.y >= 0 && next.y < 5){vis[next.x][next.y] = 1;q.push(next); } }}}
int main()
{for(int i = 0; i < 5; i++){for(int j = 0; j < 5; j++){cin >> Map[i][j];}}cout << bfs() << endl;return 0;
}
这篇关于迷宫问题~写题笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
