J - 迷宫问题（bfs求最短路径+递归输出最短路径）

迷宫问题

题意：给你一个迷宫，迷宫一定有解，让你求出最短路径，并输出此条路径。

---

解题思路：对于这种题目，我们已经见怪不怪了，关键就是要记录前驱结点，由于此题数据量小，我们可以直接使用递归来实现，如果数据量较大，就要考虑用栈来实现了。

---

AC代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<cstring>
#include<memory.h>
#include<map>
#include<iterator>
#include<list>
#include<set>
#include<functional>

using namespace std;

int maze[5][5];//由于元素只有数字，我们采用整型数组更好
int go[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
//操作行为
typedef struct node{
	int x,y;//记录坐标
}node;
bool visited[5][5];
node nodes[5][5];
void print(int x,int y){
	if(x==0&&y==0){
		cout<<"(0, 0)"<<endl;
		return;
	}
	print(nodes[x][y].x,nodes[x][y].y);
	cout<<"("<<x<<", "<<y<<")"<<endl;
}
void bfs(){
	memset(visited,false,sizeof(visited));
	node temp,head;
	head.x=0;head.y=0;
	queue<node> q;
	q.push(head);
	visited[0][0]=true;
	while(!q.empty()){
		head=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			temp.x=head.x+go[i][0];
			temp.y=head.y+go[i][1];
			if(temp.x>=0&&temp.x<5&&temp.y>=0&&temp.y<5&&!visited[temp.x][temp.y]&&maze[temp.x][temp.y]==0){
				visited[temp.x][temp.y]=true;
				nodes[temp.x][temp.y]=head;  //记录前驱结点。
				q.push(temp);
			    if(temp.x==4&&temp.y==4){
					print(4,4);
					return;
				}
			}
		}
	}
}
int main(){
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
		cin>>maze[i][j];
	bfs();
	return 0;
}