Maze

Maze

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5094

BFS+状态压缩

把身上携带钥匙的状态压缩成一个2^10的整数。这道题难在如何表示墙和门所在的位置，我是另开了个两个N*N的数组mp_r[N][N]，mp_c[N][N]分别以行和列错位存储存储墙和门的位置（mp_r[i][j]表示第r行j列和第r行j+1列的墙的状态），其他人好像是用mp[N][N][4]来存储墙和门的状态的，突然觉得我好蠢...这题坑点是一个位置可以存多把钥匙（吐血怪不得这么多次都是WA）= =

代码如下：

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #define LL long long

 #define N 55

 using namespace std;

 struct node{

     LL x,y,time;

     bool key[];

 };

 node s,e;

 LL mp_r[N][N];

 LL mp_c[N][N];

 LL key[N][N][];

 LL n,m,p;

 bool mark[][N][N];

 bool flag;

 LL dx[]={-,,,};

 LL dy[]={,,-,};

 LL zip(node t){

     LL code=;

     for(LL i=;i<p;++i)

         code=(code<<)|t.key[i];

     return code;

 }

 void init(){

     flag=;

     s.x=,s.y=,s.time=;

     e.x=n,e.y=m,e.time=;

     memset(mp_r,-,sizeof(mp_r));

     memset(mp_c,-,sizeof(mp_c));

     memset(key,,sizeof(key));

     memset(mark,,sizeof(mark));

     mark[][][]=;

     LL k;

     scanf("%I64d",&k);

     while(k--){

         LL x1,y1,x2,y2,g;

         scanf("%I64d%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2,&g);

         if(x1-x2==)mp_r[x1][(y1+y2)/]=g;

         else mp_c[(x1+x2)/][y1]=g;

     }

     scanf("%I64d",&k);

     while(k--){

         LL x,y,q;

         scanf("%I64d%I64d%I64d",&x,&y,&q);

         q--;

         key[x][y][q]=;

     }

     for(int i=;i<;i++)

     if(key[][][i])s.key[i]=;

 }

 int main(void){

     while(~scanf("%I64d%I64d%I64d",&n,&m,&p)){

         init();

         queue<node> que;

         que.push(s);

         while(!que.empty()){

             node t=que.front();

             que.pop();

             if(t.x==e.x&&t.y==e.y){

                 e.time=t.time;

                 flag=;

                 break;

             }

             for(LL i=;i<;++i){

                 LL x=t.x+dx[i];

                 LL y=t.y+dy[i];

                 if(<=x&&x<=n&&<=y&&y<=m){

                     node temp;

                     temp.x=x,temp.y=y,temp.time=t.time+;

                     for(LL j=;j<p;++j)temp.key[j]=t.key[j];

                     for(int j=;j<;j++)

                         if(key[x][y][j])temp.key[j]=;

                     if(dx[i]){

                         if(mp_c[(x+t.x)/][y]!=)

                         if(mp_c[(x+t.x)/][y]==-||temp.key[mp_c[(x+t.x)/][y]-]){

                             LL key_zip=zip(temp);

                             if(!mark[key_zip][x][y]){

                                 mark[key_zip][x][y]=;

                                 que.push(temp);

                             }

                         }

                     }else if(dy[i]){

                         if(mp_r[x][(y+t.y)/]!=)

                         if(mp_r[x][(y+t.y)/]==-||temp.key[mp_r[x][(y+t.y)/]-]){

                             LL key_zip=zip(temp);

                             if(!mark[key_zip][x][y]){

                                 mark[key_zip][x][y]=;

                                 que.push(temp);

                             }

                         }

                     }

                 }

             }

         }

         if(flag)printf("%I64d\n",e.time);

         else printf("-1\n");

     }

 }

巴特西

Maze

最新文章

热门文章