迷宫问题
Time Limit: 1000MS | | Memory Limit: 65536K |
Total Submissions: 11323 | | Accepted: 6776 |
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)
Source
题目分析：
此题的移动方向已经很明确要么下要么右
<span style="font-size:24px;">#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
int mark[7][7],map[7][7];
struct node
{
int a;
int b;
};
stack<node> q;
void bfs(int x,int y)
{
if(!mark[x][y])
{
node arr;
arr.a=x;
arr.b=y;
mark[x][y]=1;
q.push(arr);
}
if(x==5&&y==5) return ;
if(!mark[x+1][y]&&!map[x+1][y]) bfs(x+1,y);
else if(!mark[x][y+1]&&!map[x][y+1]) bfs(x,y+1);
else
{
node arr;
q.pop();
arr=q.top();
bfs(arr.a,arr.b);
}
}
int main()
{
for(int i=1;i<=5;i++)
for(int j=1;j<=5;j++)
//cin>>map[i][j];
scanf("%d",&map[i][j]);
memset(mark,0,sizeof(mark));
for(int i=0;i<7;i++)
{
map[0][i]=1;
map[i][0]=1;
map[i][6]=1;
map[6][i]=1;
}
bfs(1,1);
vector<node> v;
while(!q.empty())
{
v.push_back(q.top());
q.pop();
}
for(int i=v.size()-1;i>=0;i--)
printf("(%d, %d)\n",v[i].a-1,v[i].b-1);
return 0;
}</span>