浙江财经大学
信息管理与工程学院

HDU 1429 胜利大逃亡(续)(BFS+状态压缩)

本文由 Ocrosoft 于 2016-07-03 15:38:05 发表

胜利大逃亡(续)

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7617    Accepted Submission(s): 2683

Problem Description
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带锁的门,钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置,离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次,若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试,Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢,如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。
 

Input
每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图,其中包括:
. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙,对应的门分别为A-J
每组测试数据之间有一个空行。
 

Output
针对每组测试数据,如果可以成功逃亡,请输出需要多少分钟才能离开,如果不能则输出-1。
 

Sample Input
	
4 5 17 @A.B. a*.*. *..*^ c..b* 4 5 16 @A.B. a*.*. *..*^ c..b*
 

Sample Output
	
16 -1
 

Author
LL
 

Solution

问题在于如何记录手上持有的钥匙的状态。用vis三维数组保存。

钥匙最多10把,所以可以用二进制状压保存。按位与(&)就是开门,按位或(|)就是捡钥匙。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
char mp[30][30];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
bool vis[30][30][2048];//x,y,钥匙
int n,m,T,ex,ey;
struct node
{
    int x,y;
    int step;
    int key;
} t,tt;
bool check(int x,int y)
{
    if(x<0||y<0||x>=n||y>=m)return false;
    if(mp[x][y]=='*')return false;
    return true;
}
int bfs()
{
    queue<node> q;
    ms(vis);
    q.push(tt);
    vis[tt.x][tt.y][tt.key]=1;
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(mp[t.x][t.y]=='^')
            return t.step;
        for(int i=0; i<4; i++)
        {
            tt.x=t.x+dir[i][0],tt.y=t.y+dir[i][1];
            if(check(tt.x,tt.y))
            {
                tt.key=t.key;
                tt.step=t.step+1;
                if(tt.step>=T)continue;
                if(isupper(mp[tt.x][tt.y]))//门
                {
                    int nk=tt.key&1<<(mp[tt.x][tt.y]-'A');
                    if(nk&&!vis[tt.x][tt.y][tt.key])
                    {
                        vis[tt.x][tt.y][tt.key]=true;
                        q.push(tt);
                    }
                }
                else if(islower(mp[tt.x][tt.y]))//钥匙
                {
                    tt.key=tt.key|1<<(mp[tt.x][tt.y]-'a');
                    if(!vis[tt.x][tt.y][tt.key])
                    {
                        vis[tt.x][tt.y][tt.key]=true;
                        q.push(tt);
                    }
                }
                else
                {
                    if(!vis[tt.x][tt.y][tt.key])
                    {
                        vis[tt.x][tt.y][tt.key]=1;
                        q.push(tt);
                    }
                }
            }
        }
    }
    return -1;
}
int main()
{
    while(cin>>n>>m>>T)
    {
        for(int i=0; i<n; i++)
            cin>>mp[i];
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(mp[i][j]=='@')
                    tt.x=i,tt.y=j,tt.step=0,tt.key=0;
            }
        }
        printf("%d\n",bfs());
    }
    return 0;
}

 

欢迎分享与转载,请保留链接与出处。Ocrosoft » HDU 1429 胜利大逃亡(续)(BFS+状态压缩)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址