poj3984迷宫问题

连接：http://poj.org/problem?id=3984

描述

定义一个二维数组： 

INT迷宫[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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入

一个5×5的二维数组，表示一个迷宫。数据保证有唯一解。

产量

左上角到右下角的最短路径，格式如样例所示。

样本输入

<span style="color:#0d0d0d">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</span>

样本输出

<span style="color:#0d0d0d">（0,0）
（1,0）
（2,0）
（2,1）
（2,2）
（2,3）
（2,4）
（3,4）
（4,4）</span>

bfs样板题，但是我觉得很麻烦，可能是因为queue用的不太熟吧，很迷糊。

代码：

#include<iostream>
#include<algorithm>
#include<fstream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<cctype>
#include<vector>
#include<limits.h>
#include<queue>

using namespace std;

struct mmp
{
    int r,c;
    int par;
    mmp(int x,int y,int z):r(x),c(y),par(z) {}
};

mmp p[100]=mmp(1110,1110,-1111);
int s[10][10];
int tail=1,head=0;
int w[4][2]= {{0,1},{0,-1},{-1,0},{1,0}};
int h[100];

void bfs()
{
    int i,j=0;
    while(head!=tail)
    {
        mmp g=p[head];
        if(g.r==4&&g.c==4)
        {
            h[j++]=head;
            while(g.par!=-1)
            {
                h[j++]=g.par;
                g=p[g.par];
            }
            for(i=j-1; i>=0; i--)
            {
                printf("(%d, %d)\n",p[h[i]].r,p[h[i]].c);
            }
            break;
        }
        else
        {
            for(i=0; i<4; ++i)
            {
                int x,y;
                x=g.r+w[i][0];
                y=g.c+w[i][1];
                if(x>=0&&x<5&&y>=0&&y<5&&s[x][y]==0)
                {
                    p[tail++]=mmp(x,y,head);
                    s[x][y]=1;
                }
            }
            head++;
        }
    }
}

int main()
{
    int i,j;
    for(i=0; i<5; ++i)
    {
        for(j=0; j<5; ++j)
        {
            scanf("%d",&s[i][j]);
        }
    }
    p[0]=mmp(0,0,-1);
    bfs();
    return 0;
}