#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, d[N][N], nxt[N][N][4], f[N][N];
char a[N][N];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
bool in (int x, int y) {
return x >= 0 && x <= n + 1 && y >= 0 && y <= m + 1;
}
bool in2 (int x, int y) {
return x >= 0 && x <= n + 1 && y >= 0 && y <= m + 1 && a[x][y] != '#';
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= m + 1; j++) if (i == 0 || i == n + 1 || j == 0 || j == m + 1) a[i][j] = '#';
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++) {
if (a[i][j] == '#') nxt[i][j][0] = j;
else nxt[i][j][0] = nxt[i][j - 1][0];
}
for (int j = m + 1; j >= 0; j--) {
if (a[i][j] == '#') nxt[i][j][2] = j;
else nxt[i][j][2] = nxt[i][j + 1][2];
}
}
for (int j = 0; j <= m + 1; j++) {
for (int i = 0; i <= n + 1; i++) {
if (a[i][j] == '#') nxt[i][j][1] = i;
else nxt[i][j][1] = nxt[i - 1][j][1];
}
for (int i = n + 1; i >= 0; i--) {
if (a[i][j] == '#') nxt[i][j][3] = i;
else nxt[i][j][3] = nxt[i + 1][j][3];
}
}
memset(f, 0x3f, sizeof(f));
queue <pair <int, int> > q;
for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= m + 1; j++) if (a[i][j] == '#') f[i][j] = 0, q.push({i, j});
while (!q.empty()) {
int x = q.front().first, y = q.front().second; q.pop();
for (int i = 0; i < 4; i++) {
if (in(x + dx[i], y + dy[i]) && f[x + dx[i]][y + dy[i]] > f[x][y] + 1) {
f[x + dx[i]][y + dy[i]] = f[x][y] + 1;
q.push({x + dx[i], y + dy[i]});
}
}
}
memset(d, 0x3f, sizeof(d));
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] == 'S') d[i][j] = 0, q.push({i, j});
while (!q.empty()) {
int x = q.front().first, y = q.front().second; q.pop();
for (int i = 0; i < 4; i++) {
if (in2(x + dx[i], y + dy[i]) && d[x + dx[i]][y + dy[i]] > d[x][y] + 1) {
d[x + dx[i]][y + dy[i]] = d[x][y] + 1;
q.push({x + dx[i], y + dy[i]});
}
}
for (int i = 0; i <= 2; i += 2) {
int ny = nxt[x][y][i];
if (y < ny) {
if (in2(x, ny - 1) && d[x][ny - 1] > d[x][y] + f[x][y]) {
d[x][ny - 1] = d[x][y] + f[x][y];
q.push({x, ny - 1});
}
}
else {
if (in2(x, ny + 1) && d[x][ny + 1] > d[x][y] + f[x][y]) {
d[x][ny + 1] = d[x][y] + f[x][y];
q.push({x, ny + 1});
}
}
}
for (int i = 1; i <= 3; i += 2) {
int nx = nxt[x][y][i];
if (x < nx) {
if (in2(nx - 1, y) && d[nx - 1][y] > d[x][y] + f[x][y]) {
d[nx - 1][y] = d[x][y] + f[x][y];
q.push({nx - 1, y});
}
}
else {
if (in2(nx + 1, y) && d[nx + 1][y] > d[x][y] + f[x][y]) {
d[nx + 1][y] = d[x][y] + f[x][y];
q.push({nx + 1, y});
}
}
}
}
int ans = -1;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] == 'C') ans = d[i][j];
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8320 KB |
Output is correct |
2 |
Correct |
9 ms |
8320 KB |
Output is correct |
3 |
Correct |
10 ms |
8320 KB |
Output is correct |
4 |
Correct |
13 ms |
8320 KB |
Output is correct |
5 |
Correct |
9 ms |
8320 KB |
Output is correct |
6 |
Correct |
8 ms |
8320 KB |
Output is correct |
7 |
Correct |
8 ms |
8320 KB |
Output is correct |
8 |
Correct |
9 ms |
8320 KB |
Output is correct |
9 |
Correct |
9 ms |
8320 KB |
Output is correct |
10 |
Correct |
9 ms |
8348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8320 KB |
Output is correct |
2 |
Correct |
9 ms |
8288 KB |
Output is correct |
3 |
Correct |
9 ms |
8320 KB |
Output is correct |
4 |
Correct |
9 ms |
8320 KB |
Output is correct |
5 |
Correct |
8 ms |
8320 KB |
Output is correct |
6 |
Correct |
8 ms |
8320 KB |
Output is correct |
7 |
Correct |
9 ms |
8320 KB |
Output is correct |
8 |
Correct |
18 ms |
8320 KB |
Output is correct |
9 |
Correct |
9 ms |
8616 KB |
Output is correct |
10 |
Correct |
9 ms |
8576 KB |
Output is correct |
11 |
Correct |
9 ms |
8576 KB |
Output is correct |
12 |
Correct |
12 ms |
8576 KB |
Output is correct |
13 |
Correct |
9 ms |
8576 KB |
Output is correct |
14 |
Correct |
10 ms |
8320 KB |
Output is correct |
15 |
Correct |
9 ms |
8576 KB |
Output is correct |
16 |
Correct |
8 ms |
8320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
9 ms |
8320 KB |
Output is correct |
3 |
Correct |
8 ms |
8320 KB |
Output is correct |
4 |
Correct |
11 ms |
8320 KB |
Output is correct |
5 |
Correct |
14 ms |
10112 KB |
Output is correct |
6 |
Correct |
14 ms |
10116 KB |
Output is correct |
7 |
Correct |
14 ms |
10240 KB |
Output is correct |
8 |
Correct |
12 ms |
10240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8320 KB |
Output is correct |
2 |
Correct |
8 ms |
8292 KB |
Output is correct |
3 |
Correct |
8 ms |
8320 KB |
Output is correct |
4 |
Correct |
8 ms |
8320 KB |
Output is correct |
5 |
Correct |
8 ms |
8320 KB |
Output is correct |
6 |
Correct |
8 ms |
8320 KB |
Output is correct |
7 |
Correct |
8 ms |
8320 KB |
Output is correct |
8 |
Correct |
8 ms |
8320 KB |
Output is correct |
9 |
Correct |
9 ms |
8576 KB |
Output is correct |
10 |
Correct |
9 ms |
8576 KB |
Output is correct |
11 |
Correct |
9 ms |
8576 KB |
Output is correct |
12 |
Correct |
9 ms |
8576 KB |
Output is correct |
13 |
Correct |
8 ms |
8576 KB |
Output is correct |
14 |
Correct |
13 ms |
10112 KB |
Output is correct |
15 |
Correct |
14 ms |
10112 KB |
Output is correct |
16 |
Correct |
17 ms |
10240 KB |
Output is correct |
17 |
Correct |
15 ms |
10112 KB |
Output is correct |
18 |
Correct |
15 ms |
10112 KB |
Output is correct |
19 |
Correct |
14 ms |
9984 KB |
Output is correct |
20 |
Correct |
15 ms |
9984 KB |
Output is correct |
21 |
Correct |
13 ms |
10104 KB |
Output is correct |
22 |
Correct |
13 ms |
10112 KB |
Output is correct |
23 |
Correct |
14 ms |
10112 KB |
Output is correct |
24 |
Correct |
18 ms |
9984 KB |
Output is correct |
25 |
Correct |
8 ms |
8320 KB |
Output is correct |
26 |
Correct |
8 ms |
8576 KB |
Output is correct |
27 |
Correct |
8 ms |
8320 KB |
Output is correct |
28 |
Correct |
13 ms |
10240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
8 ms |
8320 KB |
Output is correct |
3 |
Correct |
8 ms |
8320 KB |
Output is correct |
4 |
Correct |
8 ms |
8320 KB |
Output is correct |
5 |
Correct |
8 ms |
8320 KB |
Output is correct |
6 |
Correct |
8 ms |
8320 KB |
Output is correct |
7 |
Correct |
9 ms |
8320 KB |
Output is correct |
8 |
Correct |
9 ms |
8428 KB |
Output is correct |
9 |
Correct |
9 ms |
8576 KB |
Output is correct |
10 |
Correct |
9 ms |
8576 KB |
Output is correct |
11 |
Correct |
9 ms |
8576 KB |
Output is correct |
12 |
Correct |
10 ms |
8576 KB |
Output is correct |
13 |
Correct |
9 ms |
8576 KB |
Output is correct |
14 |
Correct |
17 ms |
10112 KB |
Output is correct |
15 |
Correct |
18 ms |
10112 KB |
Output is correct |
16 |
Correct |
18 ms |
10144 KB |
Output is correct |
17 |
Correct |
25 ms |
10112 KB |
Output is correct |
18 |
Correct |
16 ms |
10112 KB |
Output is correct |
19 |
Correct |
16 ms |
9984 KB |
Output is correct |
20 |
Correct |
16 ms |
9992 KB |
Output is correct |
21 |
Correct |
16 ms |
10112 KB |
Output is correct |
22 |
Correct |
15 ms |
10112 KB |
Output is correct |
23 |
Correct |
16 ms |
10112 KB |
Output is correct |
24 |
Correct |
180 ms |
26256 KB |
Output is correct |
25 |
Correct |
279 ms |
26488 KB |
Output is correct |
26 |
Correct |
250 ms |
26076 KB |
Output is correct |
27 |
Correct |
282 ms |
26204 KB |
Output is correct |
28 |
Correct |
149 ms |
29852 KB |
Output is correct |
29 |
Correct |
153 ms |
26848 KB |
Output is correct |
30 |
Correct |
156 ms |
26872 KB |
Output is correct |
31 |
Correct |
13 ms |
9984 KB |
Output is correct |
32 |
Correct |
175 ms |
26232 KB |
Output is correct |
33 |
Correct |
8 ms |
8320 KB |
Output is correct |
34 |
Correct |
8 ms |
8576 KB |
Output is correct |
35 |
Correct |
153 ms |
27904 KB |
Output is correct |
36 |
Correct |
8 ms |
8320 KB |
Output is correct |
37 |
Correct |
13 ms |
10112 KB |
Output is correct |
38 |
Correct |
121 ms |
29012 KB |
Output is correct |
39 |
Correct |
195 ms |
30200 KB |
Output is correct |