2 shunfurh shunfurh 于 2017.01.03 18:34 提问

胜利大逃亡

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

2个回答

devmiao
devmiao   Ds   Rxr 2017.01.03 18:49
已采纳
Zhanjr
Zhanjr   2017.01.03 19:04
 #include<stdio.h>
#include<queue>
#include<iostream>
#include<cmath>
#include<string.h>
#include<math.h>
using namespace std;
char map[25][25];
int mark[25][25][1025];
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
int n,m,t,flag;
struct dian
{
    int x,y;
    int step;
    int key;    
}st,end;
int ppow(int a,int b)
 {
   int sum=1;
   for(int i=0;i<b;i++)
     sum*=a;
   return sum;      
 }
void bfs(dian st)
{
   queue<dian> p;
   dian v,vn;
   mark[st.x][st.y][st.key]=1;
   p.push(st);  
   while(!p.empty())
     {
        vn=p.front();
        p.pop();
        if(vn.x==end.x&&vn.y==end.y&&vn.step<t)
          {
             flag=1;
             printf("%d\n",vn.step);
             return;    
          } 
        for(int i=0;i<4;i++)
          {
             v.x=vn.x+dx[i];
             v.y=vn.y+dy[i];
             v.step=vn.step+1;
             v.key=vn.key;
             if(v.x>=n||v.x<0||v.y>=m||v.y<0) continue;
             if(map[v.x][v.y]=='*')  continue;
             if(mark[v.x][v.y][v.key]==1)  continue;
             if(map[v.x][v.y]>='A'&&map[v.x][v.y]<='J') 
                {
                  int k,p,a;
                  a=map[v.x][v.y]-'A';
                  p=ppow(2,a);
                  k=v.key|p;
                  if(v.key!=k)  continue;   
                }
             if(map[v.x][v.y]>='a'&&map[v.x][v.y]<='j') 
                {
                  v.key=v.key|ppow(2,map[v.x][v.y]-'a');    
                }   
             mark[v.x][v.y][v.key]=1;
             p.push(v); 

          }
     }
}
int main()
{
  while(scanf("%d%d%d",&n,&m,&t)!=EOF)
     {
      flag=0;
      memset(mark,0,sizeof(mark));
       for(int i=0;i<n;i++)
            scanf("%s",&map[i]);    
      for(int i=0;i<n;i++)
         for(int j=0;j<m;j++)
          {
            if(map[i][j]=='@')
              {
               st.x=i;
               st.y=j;
              }
             if(map[i][j]=='^')
              {
               end.x=i; 
               end.y=j; 
              }
           }
      st.step=0;
      st.key=0;
      bfs(st);  
      if(!flag)  printf("-1\n");    
     }  
}
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!