K – 迷宫问题Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64uSubmit Status Practice POJ 3984Description定义一个二维数组：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 Input0 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0Sample Output(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)
(4, 4)
//#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<vector>#include<stack>#include<cstring>#include<queue>#include<algorithm>using namespace std;const int maxn=30;const int inf=200000;#define lson rt<<1,l,m#define rson rt<<1|1,m+1,r#define For(i,n) for(int i=0;i<(n);i++)template<class T>inline T read(T&x){char c;while((c=getchar())<=32);bool ok=false;if(c=='-')ok=true,c=getchar();for(x=0; c>32; c=getchar())x=x*10+c-'0';if(ok)x=-x;return x;}template<class T> inline void read_(T&x,T&y){read(x);read(y);}template<class T> inline void write(T x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');}template<class T>inline void writeln(T x){write(x);putchar('\n');}// ——-IO template——int a[6][6];int d[6][6];struct node{int x,y;int id;node(int a,int b,int c){x=a;y=b;id=c;}};int dx[]={0,0,1,-1};int dy[]={-1,1,0,0};int p[maxn];vector<node>v[maxn];void bfs(int x,int y){queue<node> q;For(i,maxn)v[i].clear();q.push(node(x,y,0));memset(d,0,sizeof(d));memset(p,-1,sizeof(p));d[x][y]=1;p[0]=-1;int num=1;v[0].push_back(node(x,y,0));while(!q.empty()){node s=q.front();q.pop();if(s.x==4&&s.y==4){stack<node>sa;for(int i=s.id;i!=-1;i=p[i])sa.push(v[i][0]);while(!sa.empty()){printf("(%d, %d)\n",sa.top().x,sa.top().y);sa.pop();}return;}For(i,4){int xx=dx[i]+s.x;int yy=dy[i]+s.y;if(a[xx][yy]||d[xx][yy]||xx>=5||xx<0||yy>=5||yy<0)continue;q.push(node(xx,yy,num));d[xx][yy]=d[s.x][s.y]+1;p[num]=s.id;v[num].push_back(node(xx,yy,num));num++;}}}int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEint n,m,i,j,k,t;For(i,5)For(j,5)read(a[i][j]);bfs(0,0);return 0;}
放弃等于又一次可以选择的机会。
