迷宫问题

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 37583   Accepted: 21115

Description

定义一个二维数组： 

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<string>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)

int map[6][6],vis[6][6];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

struct node
{
	int x,y;                 //坐标
	int s;			 //步数 
	int l[30];		 //方向 
 };

node bfs()          //声明结构体函数，方便传递参数
{
	queue<node>q;
	node head,next;
	head.x=0;head.y=0;head.s=0;
	vis[0][0]=1;
	q.push(head);
	while(!q.empty())
	{
		head=q.front();
		q.pop();
		if(head.x==4&&head.y==4)
			return head;
		int tx,ty;
		for(int i=0;i<4;i++)
		{
			tx=head.x+dx[i];
			ty=head.y+dy[i];
			if(tx<0||tx>4||ty<0||ty>4||vis[tx][ty]||map[tx][ty])    //判否条件
				continue;
			next=head;        //继承前一个节点的路径记录
			next.x=tx;
			next.y=ty;
			next.s=head.s+1;
			next.l[head.s]=i;
			vis[tx][ty]=1;
			q.push(next);
		}
	}
	return head;
}
int main()
{
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			cin>>map[i][j];
	node ans=bfs();
	cout<<"(0, 0)"<<endl;
	int x=0,y=0;
	for(int i=0;i<ans.s;i++)
	{
		x+=dx[ans.l[i]];
		y+=dy[ans.l[i]];
		cout<<"("<<x<<", "<<y<<")"<<endl;
	}
	return 0;
}