首页 > 代码库 > HDU 1429

HDU 1429

http://acm.hdu.edu.cn/showproblem.php?pid=1429

经典的找钥匙开门走迷宫问题,把钥匙状态压缩一下,然后对迷宫bfs

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <queue>using namespace std;int n,m,t;int vis[25][25][1<<10];struct node{    int x,y,s,step;};char M[25][25];int dx[]={1,-1,0,0};int dy[]={0,0,1,-1};int gao(int x,int k){    return (x>>k)&1;}int bfs(node s){    queue <node> q;    q.push(s);    memset(vis,0,sizeof(vis));    vis[s.x][s.y][0]=1;    while(!q.empty()){        node u=q.front();        q.pop();        if(M[u.x][u.y]==^){            return u.step;        }        for(int i=0;i<4;i++){            int xx=u.x+dx[i];            int yy=u.y+dy[i];            if(xx<0 || xx>=n || yy<0 || yy>=m)continue;            if(M[xx][yy]==*)continue;            if(M[xx][yy]>=A && M[xx][yy]<=J && !(gao(u.s,M[xx][yy]-A)))continue;            node next=u;            if(M[xx][yy]>=a && M[xx][yy]<=j){                if(!gao(u.s,M[xx][yy]-a)){                    next.x=xx;next.y=yy;next.step++;next.s|=(1<<(M[xx][yy]-a));                    if(next.step<t && !vis[xx][yy][next.s]){                        vis[xx][yy][next.s]=1;                        q.push(next);                    }                }                else{                    next.x=xx;next.y=yy;next.step++;                    if(!vis[xx][yy][u.s] && next.step<t){                        vis[xx][yy][next.s]=1;                        q.push(next);                        }                }            }            else{                next.x=xx;next.y=yy;next.step++;                if(next.step<t && !vis[xx][yy][next.s]){                    vis[xx][yy][next.s]=1;                    q.push(next);                }            }        }    }    return -1;}int main(){    while(~scanf("%d%d%d",&n,&m,&t)){        for(int i=0;i<n;i++)            scanf("%s",M[i]);        node s;        for(int i=0;i<n;i++)            for(int j=0;j<m;j++)                if(M[i][j]==@)                    s.x=i,s.y=j;        s.s=0;s.step=0;        printf("%d\n",bfs(s));    }    return 0;}
View Code

 

HDU 1429