1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <stdio.h>
#include <queue>
using namespace std;
struct INFO {
short y, x, key, cost;
};
char maze[50][51];
int N, M;
short BFS(int &x, int &y) {
queue<INFO> q;
bool visit[50][50][64] = { false, };
short dx[4] = { 0,1,0,-1 };
short dy[4] = { -1,0,1,0 };
short c, k, nx, ny, i;
q.push({ y,x,0,0 });
visit[y][x][0] = true;
while (!q.empty()) {
x = q.front().x;
y = q.front().y;
k = q.front().key;
c = q.front().cost;
q.pop();
for (i = 0; i < 4; ++i) {
nx = x + dx[i];
ny = y + dy[i];
if (0 <= nx && nx < M && 0 <= ny && ny < N && !visit[ny][nx][k] && maze[ny][nx] != '#') {
visit[ny][nx][k] = true;
if (maze[ny][nx] == '1') return c + 1;
else if (maze[ny][nx] == '.')q.push({ ny,nx,k,c + 1 });
else if ('a' <= maze[ny][nx] && maze[ny][nx] <= 'f')q.push({ ny,nx,k | (1 << (maze[ny][nx] - 'a')),c + 1 });
else if ('A' <= maze[ny][nx] && maze[ny][nx] <= 'F' && (k&(1 << (maze[ny][nx] - 'A')))) q.push({ ny,nx,k,c + 1 });
}
}
}
return -1;
}
int main() {
int x = 0, y = 0;
scanf("%d %d", &N, &M);
for (int i = 0; i < N; ++i) {
scanf("%s", maze[i]);
for (int j = 0; j < M && !x && !y; ++j)
if (maze[i][j] == '0') x = j, y = i, maze[i][j] = '.';
}
printf("%d", BFS(x,y));
}
|
