首页 > ACM题库 > HDU-杭电 > HDU 1429 胜利大逃亡(续)-BFS-[解题报告] C++
2013
12-10

HDU 1429 胜利大逃亡(续)-BFS-[解题报告] C++

胜利大逃亡(续)

问题描述 :

Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……

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

输入:

每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图,其中包括:

. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙,对应的门分别为A-J

每组测试数据之间有一个空行。

输出:

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

样例输入:

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

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

样例输出:

16
-1

题意:容易理解,但要注意的地方是:如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。因为这里我贡献了一次wa。

分析:仔细阅读题目之后,会发现最多的钥匙数量为10把,所以把这个作为题目的突破口,对钥匙进行状态压缩,具体看代码实现!

代码实现:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int n,m,time,visited[25][25][1025];
int sx,sy,ex,ey,res;
int b[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char map[25][25];

struct node{
    int x;
    int y;
    int t;
    int st;
};

int check(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='*')
     return 1;
    else
     return 0;
}

void bfs()
{
    queue<node>Q;
    struct node p,temp;
    int i,j,add;
    memset(visited,0,sizeof(visited));
    p.x=sx;p.y=sy;
    p.t=0;p.st=0;
    visited[sx][sy][0]=1;
    Q.push(p);
    while(!Q.empty())
    {
        p=Q.front();
        Q.pop();
        if(p.x==ex&&p.y==ey&&p.t<time)//这里要注意下,为此贡献了一次wa
        {
            res=p.t;
            return ;
        }
        if(p.t>=time)
         return ;
        for(i=0;i<4;i++)
        {
            temp.x=p.x+b[i][0];
            temp.y=p.y+b[i][1];
            temp.t=p.t+1;
            temp.st=p.st;
            if(check(temp.x,temp.y))
            {
                if(map[temp.x][temp.y]>='a'&&map[temp.x][temp.y]<='j')
                {
                    add=1<<(map[temp.x][temp.y]-'a');
                    temp.st=temp.st|add;
                    if(visited[temp.x][temp.y][temp.st]==0)
                    {
                        visited[temp.x][temp.y][temp.st]=1;
                        Q.push(temp);
                    }
                }
                else if(map[temp.x][temp.y]>='A'&&map[temp.x][temp.y]<='J')
                {
                    add=1<<(map[temp.x][temp.y]-'A');
                    if((temp.st&add)&&visited[temp.x][temp.y][temp.st]==0)
                    {
                        visited[temp.x][temp.y][temp.st]=1;
                        Q.push(temp);
                    }
                }
                else if(visited[temp.x][temp.y][temp.st]==0)
                {
                    visited[temp.x][temp.y][temp.st]=1;
                    Q.push(temp);
                }
            }
        }
    }
}

int main()
{
    int i,j;
    while(scanf("%d%d%d",&n,&m,&time)!=EOF)
    {
        res=-1;
        for(i=1;i<=n;i++)
        {
            getchar();
            for(j=1;j<=m;j++)
            {
                scanf("%c",&map[i][j]);
                if(map[i][j]=='@')
                {
                    sx=i;
                    sy=j;
                }
                else if(map[i][j]=='^')
                {
                    ex=i;
                    ey=j;
                }
            }
        }
        bfs();
        printf("%d\n",res);
    }
    return 0;
}

 

解题报告转自:http://www.cnblogs.com/jiangjing/p/3450185.html


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  3. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……