### Problem Description

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

#### Input

. 代表路

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

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

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

16
-1

### 代码如下

#include <bits/stdc++.h>
#define inf 2147483647
using namespace std;
char mp[25][25];
int f[25][25][1 << 10], vis[25][25], V[25][25];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct node{
int x,  y;
};
int main(){
int i, j, k, n, m, T, tx, ty, x, y, u, v, flag, ans;
node s, t;
while(scanf("%d%d%d", &n, &m, &T) != EOF){
ans = inf;
queue<node> q;
memset(f, 0, sizeof(f));
for(i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
if(mp[i][j] == '@') s.x = i, s.y = j, q.push(s), f[i][j][0] = 1;
if(mp[i][j] == '^') tx = i, ty = j;
}
}
while(!q.empty()){
s = q.front(); q.pop();
x = s.x; y = s.y;
V[x][y]++;
vis[x][y] = 0;
//printf("%d %d====\n", x, y);
for(i = 0; i <= 3; i++){
u = x + dx[i];
v = y + dy[i];
flag = 0;
if(u >= 1 && u <= n && v >= 1 && v <= m){
//printf("%d %d=====\n", u, v);
if(mp[u][v] == '*') continue;
if(mp[u][v] == '.' || mp[u][v] == '^' || mp[u][v] == '@'){
for(k = 0; k < (1 << 10); k++){
if(f[x][y][k] && !f[u][v][k]) flag = 1, f[u][v][k] = f[x][y][k] + 1;
}
if(flag && !vis[u][v]) vis[u][v] = 1, t.x = u, t.y = v, q.push(t);
}
if(mp[u][v] >= 'a' && mp[u][v] <= 'j'){
j = mp[u][v] - 'a';
for(k = 0; k < (1 << 10); k++){
if(!((1 << j) & k)) continue;
if(f[x][y][k ^ (1 << j)] && !f[u][v][k]) f[u][v][k] = f[x][y][k ^ (1 << j)] + 1, flag = 1;
if(f[x][y][k] && !f[u][v][k]) flag = 1, f[u][v][k] = f[x][y][k] + 1;
}
if(flag && !vis[u][v]) vis[u][v] = 1, t.x = u, t.y = v, q.push(t);
}
if(mp[u][v] >= 'A' && mp[u][v] <= 'J'){
j = mp[u][v] - 'A';
for(k = 0; k < (1 << 10); k++){
if(!((1 << j) & k)) continue;
if(f[x][y][k] && !f[u][v][k]){
flag = 1, f[u][v][k] = f[x][y][k] + 1;
/*if(u == 6 && v == 1){
printf("%d %d\n", k, f[6][1][k]);
}*/
}
}
if(flag && !vis[u][v]) vis[u][v] = 1, t.x = u, t.y = v, q.push(t);
}
}
}
}
/*for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
printf("%d ", V[i][j]);
}
printf("\n");
}*/
//printf("===%d %d\n", tx, ty);
for(k = 0; k < (1 << 10); k++) if(f[tx][ty][k]) ans = min(ans, f[tx][ty][k]);
//printf("=======%d\n", ans);
if(ans - 1 >= T) printf("-1\n");
else printf("%d\n", ans - 1);
}
return 0;
}