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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #include <iostream>
#include <list>
#define INF 2000000000
using namespace std;
int n, m, os[2] = { 1, -1 }, visit[500][500][2], ans = INF;
char map[500][500];
pair<int, int> c;
list<pair<pair<int, int>, pair<bool, int>>> l;
bool meetD;
bool fall(bool g, int* r, int* c);
void bfs();
void afterCheck(int *r, int *c, bool g, int f);
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
map[i][j] = s[j];
if (s[j] == 'C')
c = { i, j };
visit[i][j][0] = visit[i][j][1] = INF;
}
}
if (!fall(0, &c.first, &c.second)) {
cout << -1;
return 0;
}
bfs();
if (ans != INF)
cout << ans;
else
cout << -1;
}
bool fall(bool g, int* r, int* c) {
while (((g == 0 && *r < n - 1) || (g == 1 && *r > 0)) && map[*r + os[g]][*c] != '#') {
if (map[*r][*c] == 'D')
meetD = true;
*r += os[g];
}
if (map[*r][*c] == 'D')
meetD = true;
if ((g == 0 && *r == n - 1) || (g == 1 && *r == 0))
return false;
return true;
}
void bfs() {
l.push_back({ {c.first, c.second}, {0,0} });
visit[c.first][c.second][0] = 0;
while (!l.empty()) {
int cr = l.front().first.first, cc = l.front().first.second, g = l.front().second.first, f = l.front().second.second;
l.pop_front();
if (map[cr][cc] == 'D') {
ans = min(ans, f);
continue;
}
for (int i = 0; i < 2; i++) {
int nr = cr, nc = cc + os[i];
if (nc >= 0 && nc < m && f < visit[nr][nc][g] && map[nr][nc] != '#')
afterCheck(&nr, &nc, g, f);
}
if (++f < visit[cr][cc][!g])
afterCheck(&cr, &cc, !g, f);
}
}
void afterCheck(int* r, int* c, bool g, int f) {
visit[*r][*c][g] = f;
bool temp = fall(g, r, c);
if (meetD) {
meetD = false;
ans = min(ans, f);
}
else if (temp) {
visit[*r][*c][g] = f;
l.push_back({ {*r,*c}, {g, f} });
}
}
|
