poj 2049 Finding Nemo(搜索)

http://poj.org/problem?id=2049
/*   我认为这是一道非常好的搜索题，
第一次使用到了优先队列，（是更新的距离最短），0代表空 1代表 们  inf 代表wall 用h[][]
存储行的信息，l[][],存储列的信息
｛学到的新知识，对于这种一方格作为点的 图 用两个二维图分别存储变得信息｝
*/


#include<cstdio>
#include<cstring>

#include<queue>
using namespace std;
#define maxn 250
#define inf 99999999
struct node
{
    int x;
    int y;
    int len;
    bool operator <(const node &a)const
    {
        return len>a.len;
    }
};

int n,m,sx,sy,xmax,ymax;
int dis[maxn][maxn],h[maxn][maxn],l[maxn][maxn];
priority_queue<node>q;
void bfs()
{
    int x,y;
    for(x=0;x<=xmax;x++)
    {
        for(y=0;y<=ymax;y++)
        {
            dis[x][y]=inf;
        }
    }
    while(!q.empty())q.pop();
    node pn;
    pn.x=0;pn.y=0;pn.len=0;
    dis[0][0]=0;
    q.push(pn);
    while(!q.empty())
    {
        pn=q.top();
        q.pop();
        x=pn.x;y=pn.y;
        if(x==sx&&y==sy)return ;
        //向上走
        if(y+1<=ymax&&dis[x][y+1]>dis[x][y]+h[x][y+1])
        {
            dis[x][y+1]=dis[x][y]+h[x][y+1];
            pn.x=x;pn.y=y+1;pn.len=dis[x][y+1];
            q.push(pn);
        }
        //向下走
        if(y-1>=0&&dis[x][y-1]>dis[x][y]+h[x][y])
        {
            dis[x][y-1]=dis[x][y]+h[x][y];
            pn.x=x;pn.y=y-1;pn.len=dis[x][y-1];
            q.push(pn);
        }
        //想左走
        if(x-1>=0&&dis[x-1][y]>dis[x][y]+l[x][y])
        {
            dis[x-1][y]=dis[x][y]+l[x][y];
            pn.x=x-1;pn.y=y;pn.len=dis[x-1][y];
            q.push(pn);
        }
        //向右走
        if(x+1<=xmax&&dis[x+1][y]>dis[x][y]+l[x+1][y])
        {
            dis[x+1][y]=dis[x][y]+l[x+1][y];
            pn.x=x+1;pn.y=y;pn.len=dis[x+1][y];
            q.push(pn);
        }
    }
    dis[sx][sy]=-1;


}

int main()
{
    int i,j,x,y,d,t;
    double tx,ty;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(m==-1&&n==-1)break;
        xmax=ymax=-1;
        memset(h,0,sizeof(h));
        memset(l,0,sizeof(l));
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x,&y,&d,&t);
            if(d==0)
            {
                for(j=0;j<t;j++)
                {
                    h[x+j][y]=inf;
                }
                xmax=max(xmax,x+t);
                ymax=max(ymax,y);

            }
            else
            {
                for(j=0;j<t;j++)
                {
                    l[x][y+j]=inf;
                }
                xmax=max(xmax,x);
                ymax=max(ymax,y+t);
            }
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&d);
            if(d==0)
            {
                h[x][y]=1;
            }
            else l[x][y]=1;
        }
       scanf("%lf%lf",&tx,&ty);
       if(tx>xmax||ty>ymax)
       {
           printf("0\n");
       }
       else
       {
           sx=(int)tx;
           sy=(int)ty;
           bfs();

           printf("%d\n",dis[sx][sy]);
       }
    }
}