POJ 2049 Finding Nemo BFS 三维数组存状态, 优先队列优化时间与空间

点击打开链接

题目大意：有一个迷宫，在迷宫中有墙与门
有m道墙，每一道墙表示为(x,y,d,t）
x,y表示墙的起始坐标
d为0即向右t个单位，都是墙
d为1即向上t个单位，都是墙
有n道门，每一道门表示为(x,y,d)
x,y表示门的起始坐标
d为0即向右一个单位表示门
d为1即向上一个单位表示门
再给出你起点的位置(f1,f2)，并保证这个点的位置不会再墙或者门中，为起点到(0,0)最少要穿过多少条门

周围的其他地方都是空地，在空地上行走是不浪费步数的。

思路是：

可以从终点去bfs找到达（0,0）点的最短路，遇到门就步数加1 ，遇到空地 步数不变位置改变，

遇到墙不可以行走了。

对于每一个点小方格都可以用左下角（x,y）的坐标来表示，然后用四个变量分别表示该空格的四周的状态，（用0,1,2,3分别表示左上右下）  每个空格四周的状态又分为（0,1，INF,分别表示空地，有门，有墙）

刚开始用普通的队列，边界条件没判断好，出现了MLE，改用priority_queue ,之后WA，结果是符号的重载，重载反了，最后交C++，wa，然后改用G++交就ac。

注意，对于ma[][][]的坐标的选取问题，一定要画图进行选取，否则会取颠倒

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define INF 0x3f3f3f3f
#define bug puts("*****************")
using namespace std;

const int NN=220;
int ma[NN][NN][4];
int vis[NN][NN];
int n,m,Min;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
struct node{
    int x,y,step;
    node(){};
    node (int a,int b,int c){
        x=a;
        y=b;
        step=c;
    }
    friend bool operator <(node p1,node p2){  
        return p1.step>p2.step;  ///认清重载符合
    }
};
priority_queue<node,vector<node>,less<node> >Q;

int judge(int x,int y){
    if(x<0||y<0||x>199||y>199) return 0;
    return 1;
}

void BFS(int x,int y){

    while(!Q.empty()) Q.pop();
    node no,temp;
    vis[x][y]=1;
    no.x=x;
    no.y=y;
    no.step=0;
    Q.push(no);
    while(!Q.empty()){
        no=Q.top();
        Q.pop();
       // cout<<no.x<<"  "<<no.y<<endl;
        if(no.x==0&&no.y==0){
            Min=min(Min,no.step);
            break;
        }
        if(no.step>=Min) continue;
      //  cout<<no.step<<endl;
        for(int i=0;i<4;i++){       ///四周
            if(ma[no.x][no.y][i]==1){
                temp.x=no.x+dx[i];   ///dx[i]方向与i对应
                temp.y=no.y+dy[i];
                temp.step=no.step+1;
                if(!vis[temp.x][temp.y]&&judge(temp.x,temp.y)){   ///遇到门的情况
                    vis[temp.x][temp.y]=1;
                   // cout<<temp.x<<"  "<<temp.y<<endl;
                    Q.push(temp);
                }
            }
            else if(ma[no.x][no.y][i]==0){     ///空地情况
                temp.x=no.x+dx[i]; 
                temp.y=no.y+dy[i];
                temp.step=no.step;
                if(!vis[temp.x][temp.y]&&judge(temp.x,temp.y)){
                    vis[temp.x][temp.y]=1;
                    Q.push(temp);
                 }
            }
        }

    }
   // cout<<Min<<endl;
   printf(Min==INF?"-1
":"%d
",Min);
}
int main(){
    int u,v,d,t;
//    Q.push(node(1,2,1));
//
//    Q.push(node(2,1,4));
//    Q.push(node(2,4,7));
//    cout<<(Q.top()).step<<endl;
    while(~scanf("%d%d",&n,&m)&&(!(n+1==0&&m+1==0))){
        memset(ma,0,sizeof(ma));
        memset(vis,0,sizeof(vis));
        Min=INF;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&u,&v,&d,&t);
            if(d==0){
               for(int j=0;j<t;j++) ma[u+j][v][3]=ma[u+j][v-1][1]=INF;  ///刚开始方向写反了
                //cout<<u<<" "<<v<<" "<<u-1<<" "<<endl;
            }
            else{
               for(int j=0;j<t;j++) ma[u][v+j][0]=ma[u-1][v+j][2]=INF;
            }
        }
        for(int j=1;j<=m;j++){
            scanf("%d%d%d",&u,&v,&d);
            if(d==0) ma[u][v][3]=ma[u][v-1][1]=1;
            else  ma[u][v][0]=ma[u-1][v][2]=1;
        }
        double x,y;
        scanf("%lf%lf",&x,&y);

        int xsta=(int)x;
        int ysta=(int)y;

        if(!judge(xsta,ysta))
            puts("0");
        else{
            BFS(xsta,ysta);
        }
    }
    return 0;
}