hdu-1429 胜利大逃亡(续)

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

第一次接触搜索+状态压缩    看了大神的题解  勉强把题目弄懂了。

用二进制来表示手头的钥匙有哪些,100表示有第三把钥匙,111表示有第三、二、一把,搜索下一点时,如果该点为钥匙点,则可采用|运算来

模拟拾取,显然0001 | 1000 = 1001,同理,当为相应的门时采用&运算来模拟开启,例如1101 & 0001 = 0001(即可以打开‘A‘门)

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,t,ans;
char map[25][25];
int vis[25][25][1030];//标记数组
int dir[4][2]={-1,0,1,0,0,1,0,-1}; //四个方向
struct point
{
    int x,y,step,key;
};
point s;
int check(int x,int y)//检查
{
    if(s.x>=0&&s.x<n&&s.y>=0&&s.y<m)
        return 1;
    return 0;
}
void bfs()
{
    point tp;
    queue<point>q;
    vis[s.x][s.y][s.key]=1;
    for(q.push(s);!q.empty();q.pop())
    {
        tp=q.front();
        for(int k=0;k<4;k++)
        {
            s=tp; //注意这里要先把tp赋值给s,即先把上次搜索到的保存下来,再去扩展。
            s.x=tp.x+dir[k][0];
            s.y=tp.y+dir[k][1];
            if(check(s.x,s.y)&&map[s.x][s.y]!='*'&&!vis[s.x][s.y][s.key])
            {
                if(map[s.x][s.y]=='.'||map[s.x][s.y]=='@')
                {
                    vis[s.x][s.y][s.key]=1;
                    s.step++;
                    q.push(s);
                }
                if(map[s.x][s.y]=='^')
                {
                    if(s.step+1<t)
                        ans=s.step+1;
                    return;
                }
                if(map[s.x][s.y]>='A'&&map[s.x][s.y]<='J')
                {//a<<2表示将a是二进制左移2位(相当于*4),这里用来表示钥匙eg:A-A=0;1<<0,就是0000 0001就是第一把钥匙了。
                //同理当g[s.x][s.y]='B'时,就是1<<2,就是0000 0010,表示第二把钥匙;
                    int key=1<<(map[s.x][s.y]-'A');//按位于运算,当有对应的钥匙时,等式成立;才能打开门
                    if(s.key&key)
                    {
                        vis[s.x][s.y][s.key]=1;
                        s.step+=1;
                        q.push(s);
                    }
                }
                if(map[s.x][s.y]>='a'&&map[s.x][s.y]<='j')
                {  //按位或运算,吸收钥匙;
                    int key=1<<(map[s.x][s.y]-'a');
                    if(!vis[s.x][s.y][s.key|key])
                    {
                        vis[s.x][s.y][s.key|key]=1;
                        s.step+=1;
                        s.key=s.key|key;
                        q.push(s);
                    }
                }
            }
        }
    }

}

int main()
{
    while(scanf("%d%d%d",&n,&m,&t)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        ans=-1;
        for(int i=0;i<n;i++)
        {
            scanf("%s",map[i]);
            for(int j=0;j<m;j++)
            {
                if(map[i][j]=='@')
                {
                    s.x=i;
                    s.y=j;
                    s.key=0;
                    s.step=0;
                }
            }
        }
        bfs();
        printf("%d\n",ans);
    }
    return 0;
}

hdu-1429 胜利大逃亡(续),布布扣,bubuko.com

时间: 05-29

hdu-1429 胜利大逃亡(续)的相关文章

HDU 1429 胜利大逃亡(续)(bfs)

胜利大逃亡(续) Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6270    Accepted Submission(s): 2177 Problem Description Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)-- 这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了

HDOJ 题目1429 胜利大逃亡(续)(BFS)

New! 关于举办校第十五届程序设计竞赛暨2015省赛集训队选拔赛的通知 胜利大逃亡(续) Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5811    Accepted Submission(s): 2027 Problem Description Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)-- 这次魔王汲取了上次

胜利大逃亡(续)(状态压缩bfs)

胜利大逃亡(续) Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7357    Accepted Submission(s): 2552 Problem Description Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带

HDU 1253 胜利大逃亡(BFS)

#include <iostream> #include <cstdlib> #include <cstdio> #include <queue> #include <cstring> using namespace std; struct node{ int x,y,z,step; }; int ma[51][51][51]; int A,B,C,T; int mv[6][3] = {{1,0,0},{0,1,0},{0,0,1},{-1,0,

HDU 1253 胜利大逃亡 NYOJ 523【BFS】

胜利大逃亡 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 24608    Accepted Submission(s): 9427 Problem Description Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会. 魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的

[ACM] hdu 1253 胜利大逃亡 (三维BFS)

胜利大逃亡 Problem Description Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会. 魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出

HDU 1429--胜利大逃亡(续)【BFS &amp;&amp; 状态压缩】

胜利大逃亡(续) Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6656    Accepted Submission(s): 2315 Problem Description Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)-- 这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了

HDU 1429--胜利大逃亡(续)【BFS &amp;amp;&amp;amp; 状态压缩】

胜利大逃亡(续) Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6656    Accepted Submission(s): 2315 Problem Description Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)-- 这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了

HDU 1253 胜利大逃亡

胜利大逃亡 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 30841    Accepted Submission(s): 11509 Problem Description Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会. 魔 王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C