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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <bits/stdc++.h>
using namespace std;
const int LEN = 350;
int N, M, vis[LEN][LEN], walk[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
char arr[LEN][LEN];
struct Node
{
int x_, y_, time_;
Node(int x = 0, int y = 0, int time = 0) : x_(x), y_(y), time_(time) {}
};
queue<Node> q;
pair<Node, Node> p[27];
Node bg, ed;
void bfs()
{
q.emplace(bg.x_, bg.y_, 0);
vis[bg.x_][bg.y_] = 1;
while (!q.empty())
{
Node u = q.front();
q.pop();
int ux = u.x_, uy = u.y_, ut = u.time_;
if (ux == ed.x_ && uy == ed.y_)
{
cout << ut;
break;
}
for (int i = 0; i < 4; ++i)
{
int x = ux + walk[i][0], y = uy + walk[i][1];
char chr = arr[x][y];
if (x < 1 || x > N || y < 1 || y > M || vis[x][y] || chr == '#')
continue;
if (isalpha(chr))
{
int nxt_x = p[chr - 'A'].first.x_ == x ? p[chr - 'A'].second.x_ : p[chr - 'A'].first.x_;
int nxt_y = p[chr - 'A'].first.y_ == y ? p[chr - 'A'].second.y_ : p[chr - 'A'].first.y_;
q.emplace(nxt_x, nxt_y, ut + 1);
}
else
{
vis[x][y] = 1;
q.emplace(x, y, ut + 1);
}
}
}
}
int main()
{
cin >> N >> M;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
{
cin >> arr[i][j];
if (isalpha(arr[i][j]))
{
if (!p[arr[i][j] - 'A'].first.x_)
p[arr[i][j] - 'A'].first.x_ = i, p[arr[i][j] - 'A'].first.y_ = j;
else
p[arr[i][j] - 'A'].second.x_ = i, p[arr[i][j] - 'A'].second.y_ = j;
}
else if (arr[i][j] == '@')
{
bg.x_ = i, bg.y_ = j;
}
else if (arr[i][j] == '=')
{
ed.x_ = i, ed.y_ = j;
}
}
bfs();
return 0;
}
|