#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4e3 + 5;
int n, m, d[N][N], rab = 0, fox = 0;
char grid[N][N];
vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
deque<pair<int, pair<int, int>>> dq;
bool inbound(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m && grid[x][y] != '.';
}
void bfs() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[i][j] = 1e18;
}
}
dq.push_front({1, {1, 1}});
d[1][1] = 1;
while (dq.size()) {
int p = dq.front().first, x = dq.front().second.first, y = dq.front().second.second; dq.pop_front();
if (p != d[x][y]) continue;
for (int k = 0; k < 4; k++) {
int tox = x + dx[k], toy = y + dy[k];
if (!inbound(tox, toy)) continue;
int c = grid[x][y] != grid[tox][toy];
if (d[tox][toy] <= d[x][y] + c) continue;
d[tox][toy] = d[x][y] + c;
if (c) dq.push_back({d[tox][toy], {tox, toy}});
else dq.push_front({d[tox][toy], {tox, toy}});
}
}
cout << max(d[n][m], rab + fox) << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> grid[i][j];
if (grid[i][j] == 'R') rab = 1;
if (grid[i][j] == 'F') fox = 1;
}
}
bfs();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
6544 KB |
Output isn't correct |
2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
3 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
4 |
Incorrect |
10 ms |
6232 KB |
Output isn't correct |
5 |
Incorrect |
5 ms |
3288 KB |
Output isn't correct |
6 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
7 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
8 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
9 |
Incorrect |
1 ms |
1236 KB |
Output isn't correct |
10 |
Incorrect |
4 ms |
2900 KB |
Output isn't correct |
11 |
Incorrect |
3 ms |
2384 KB |
Output isn't correct |
12 |
Incorrect |
7 ms |
3528 KB |
Output isn't correct |
13 |
Incorrect |
4 ms |
3284 KB |
Output isn't correct |
14 |
Incorrect |
4 ms |
3288 KB |
Output isn't correct |
15 |
Incorrect |
14 ms |
6480 KB |
Output isn't correct |
16 |
Incorrect |
17 ms |
6484 KB |
Output isn't correct |
17 |
Incorrect |
12 ms |
6280 KB |
Output isn't correct |
18 |
Incorrect |
10 ms |
6228 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
31220 KB |
Output isn't correct |
2 |
Incorrect |
60 ms |
24080 KB |
Output isn't correct |
3 |
Incorrect |
402 ms |
146452 KB |
Output isn't correct |
4 |
Incorrect |
112 ms |
48204 KB |
Output isn't correct |
5 |
Incorrect |
231 ms |
99616 KB |
Output isn't correct |
6 |
Incorrect |
923 ms |
189536 KB |
Output isn't correct |
7 |
Incorrect |
15 ms |
32596 KB |
Output isn't correct |
8 |
Incorrect |
15 ms |
31188 KB |
Output isn't correct |
9 |
Incorrect |
3 ms |
980 KB |
Output isn't correct |
10 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
11 |
Incorrect |
15 ms |
31956 KB |
Output isn't correct |
12 |
Incorrect |
2 ms |
1620 KB |
Output isn't correct |
13 |
Incorrect |
61 ms |
23996 KB |
Output isn't correct |
14 |
Incorrect |
36 ms |
15472 KB |
Output isn't correct |
15 |
Incorrect |
36 ms |
16956 KB |
Output isn't correct |
16 |
Incorrect |
30 ms |
9196 KB |
Output isn't correct |
17 |
Incorrect |
152 ms |
51972 KB |
Output isn't correct |
18 |
Incorrect |
136 ms |
51336 KB |
Output isn't correct |
19 |
Incorrect |
115 ms |
48200 KB |
Output isn't correct |
20 |
Incorrect |
94 ms |
44484 KB |
Output isn't correct |
21 |
Incorrect |
243 ms |
102748 KB |
Output isn't correct |
22 |
Incorrect |
230 ms |
99728 KB |
Output isn't correct |
23 |
Incorrect |
292 ms |
86140 KB |
Output isn't correct |
24 |
Incorrect |
239 ms |
101312 KB |
Output isn't correct |
25 |
Incorrect |
653 ms |
146524 KB |
Output isn't correct |
26 |
Correct |
615 ms |
277236 KB |
Output is correct |
27 |
Incorrect |
762 ms |
233584 KB |
Output isn't correct |
28 |
Incorrect |
906 ms |
189820 KB |
Output isn't correct |
29 |
Incorrect |
887 ms |
178276 KB |
Output isn't correct |
30 |
Incorrect |
836 ms |
202900 KB |
Output isn't correct |
31 |
Incorrect |
661 ms |
112568 KB |
Output isn't correct |
32 |
Incorrect |
706 ms |
204516 KB |
Output isn't correct |