胜利大逃亡(续)

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 4328    Accepted Submission(s): 1458

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

题意：！！魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。

         题意略坑，我以为是，可以先用t时间去取尽可能多的钥匙，然后，被抓回原地，

　　   然后寻找一条最短的路。

　　　题意是： 用t的时间，包括了找钥匙的时间也算在内。(⊙o⊙)…

每个点dp[ x ] [ y ] [ state ];有这么多的状态。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7   8 struct node  9 { 10     int x,y; 11     int s_time; 12     int state; 13 }; 14 char a[22][22]; 15 int sx,sy; 16 int n,m,T; 17 int map1[4][2]={ {
    1,0},{
    0,1},{
    0,-1},{-1,0} }; 18 bool dp[21][21][(1<<10)]; 19 queue
           
            Q; 20 21 int bfs() 22 { 23 int i,x,y; 24 node cur,now; 25 cur.x=sx; 26 cur.y=sy; 27 cur.s_time=0; 28 cur.state=0; 29 Q.push(cur); 30 dp[sx][sy][cur.state]=true; 31 while(!Q.empty()) 32 { 33 cur=Q.front(); 34 Q.pop(); 35 for(i=0;i<4;i++) 36 { 37 x=cur.x+map1[i][0]; 38 y=cur.y+map1[i][1]; 39 if(x>=1&&x<=n && y>=1&&y<=m && a[x][y]!='*') 40 { 41 now.x=x; 42 now.y=y; 43 now.state=cur.state; 44 now.s_time=cur.s_time+1; 45 if(now.s_time>=T) continue; 46 if( a[x][y]=='^' && now.s_time
            
             ='A' && a[x][y]<='J' ) 51 { 52 int state=(1<<(a[x][y]-'A')); 53 if( (now.state&state)==state && dp[x][y][now.state]==false ) 54 { 55 dp[x][y][now.state]=true; 56 Q.push(now); 57 } 58 } 59 else if(a[x][y]>='a' && a[x][y]<='j') 60 { 61 int state=(1<<(a[x][y]-'a')); 62 now.state=(now.state|state); 63 if( dp[x][y][now.state]==false ) 64 { 65 dp[x][y][now.state]=true; 66 Q.push(now); 67 } 68 } 69 else if( dp[x][y][now.state]==false ) 70 { 71 dp[x][y][now.state]=true; 72 Q.push(now); 73 } 74 } 75 } 76 } 77 return -1; 78 } 79 int main() 80 { 81 int i,j; 82 while(scanf("%d%d%d",&n,&m,&T)>0) 83 { 84 for(i=1; i<=n; i++) 85 scanf("%s",a[i]+1); 86 for(i=1; i<=n; i++) 87 for(j=1; j<=m; j++) 88 if(a[i][j]=='@') 89 { 90 sx=i; 91 sy=j; 92 } 93 while(!Q.empty()) 94 { 95 Q.pop(); 96 } 97 memset(dp,false,sizeof(dp)); 98 printf("%d\n",bfs()); 99 }100 return 0;101 }