bfs+状态压缩
思路：用2进制表示每个钥匙是否已经被找到。、
/*
bfs+状态压缩
思路：用2进制表示每个钥匙是否已经被找到。
*/
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int inf = 0x3f3f3f3f;
const double pi=acos(-1.0);
const int dx[]={,-,,};
const int dy[]={,,,-};
const double eps = 1e-;
const int maxm = (<<)+;
const int maxn = ; bool vis[ maxn ][ maxn ][ maxm ];
char mat[ maxn ][ maxn ];
struct Point {
int x,y,ti,key;
};
Point s,e;
queue<Point>q; int bfs( int n,int m,int sumT ){
memset( vis,false,sizeof( vis ) );
while( !q.empty() )
q.pop();
Point cur;
cur = s;
vis[ cur.x ][ cur.y ][ cur.key ] = true;
q.push( cur );
while( !q.empty() ){
cur = q.front();
q.pop();
if( cur.x==e.x && cur.y==e.y ){
e.ti = min( e.ti,cur.ti );
}
if( cur.ti>=sumT ) continue;
for( int i=;i<;i++ ){
Point nxt ;
nxt.x = cur.x + dx[ i ];
nxt.y = cur.y + dy[ i ];
nxt.ti = cur.ti + ;
nxt.key = cur.key;
if( nxt.x<||nxt.x>=n||nxt.y<||nxt.y>=m ) continue;
if( mat[ nxt.x ][ nxt.y ]=='*' ) continue;
if( mat[ nxt.x ][ nxt.y ]>='a' && mat[ nxt.x ][ nxt.y ]<='z' ){
nxt.key = cur.key|(<<(mat[ nxt.x ][ nxt.y ]-'a'));
}//there may be a new key
if( vis[ nxt.x ][ nxt.y ][ nxt.key ]==true )
continue;
vis[ nxt.x ][ nxt.y ][ nxt.key ] = true;
if( mat[ nxt.x ][ nxt.y ]>='A' && mat[ nxt.x ][ nxt.y ]<='Z' ){
if( nxt.key&(<<(mat[ nxt.x ][ nxt.y ]-'A')) ){
q.push( nxt );
}
}
else
q.push( nxt );
}
}
if( e.ti>=sumT )
return -;
else
return e.ti;
} int main(){
int n,m,sumT;
while( scanf("%d%d%d",&n,&m,&sumT)== ){
for( int i=;i<n;i++ ){
scanf("%s",mat[ i ]);
for( int j=;j<m;j++ ){
if( mat[ i ][ j ]=='@' ){
s.x = i;
s.y = j;
s.ti = ;
s.key = ;
mat[ i ][ j ] = '.';
}
if( mat[ i ][ j ]=='^' ){
e.x = i;
e.y = j;
e.ti = sumT+;
mat[ i ][ j ] = '.';
}
}
}
printf("%d\n",bfs( n,m,sumT ));
}
return ;
}