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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1001, INF = 0x3f3f3f3f;
int n, m, dist[3][N][N], ds[5] = {1, 0, -1, 0, 1}, ans = INF;
char g[N][N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) scanf("%s", g[i]);
memset(dist, 0x3f, sizeof(dist));
for (int c = '1'; c <= '3'; ++c) {
int idx = c - '1';
deque<pair<int, int>> q;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (g[i][j] == c) {
dist[idx][i][j] = 0;
q.emplace_back(i, j);
}
while (q.size()) {
auto [x, y] = q.front(); q.pop_front();
for (int i = 0; i < 4; ++i) {
int nx = x + ds[i], ny = y + ds[i + 1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == '#') continue;
int d = g[nx][ny] == '.';
if (dist[idx][nx][ny] > dist[idx][x][y] + d) {
dist[idx][nx][ny] = dist[idx][x][y] + d;
if (d) q.emplace_back(nx, ny);
else q.emplace_front(nx, ny);
}
}
}
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (dist[0][i][j] != INF && dist[1][i][j] != INF && dist[2][i][j] != INF)
if (g[i][j] == '.') ans = min(ans, dist[0][i][j] + dist[1][i][j] + dist[2][i][j] - 2);
else ans = min(ans, dist[0][i][j] + dist[1][i][j] + dist[2][i][j]);
printf("%d", ans == INF ? -1 : ans);
return 0;
}
|