#include <bits/stdc++.h>
#define MAXH 4000
#define MAXW 4000
using namespace std;
typedef pair<int, int> ii;
int n, h, w;
int meadow[MAXH + 2][MAXW + 2];
bool visited[MAXH + 2][MAXW + 2];
int dist[MAXH + 2][MAXW + 2];
int ans;
bool isanimal(ii a)
{
return meadow[a.first][a.second] != 0;
}
int calcfunc(ii a, ii b)
{
int type1 = meadow[a.first][a.second];
int type2 = meadow[b.first][b.second];
if ( type1 == 0 || type2 == 0)
return 1e9;
return !(type1 == type2);
}
void mod_dijkstra(ii start)
{
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
dist[i][j] = 1e9;
deque<ii> q;
dist[start.first][start.second] = 1;
q.push_front(start);
while (!q.empty()) {
ii node = q.front(); q.pop_front();
if (visited[node.first][node.second])
continue;
visited[node.first][node.second] = true;
ans = max(ans, dist[node.first][node.second]);
ii neigh;
if (node.first > 0) {
neigh = node;
neigh.first--;
if (isanimal(neigh)) {
int d = calcfunc(node, neigh);
if (dist[neigh.first][neigh.second] > d + dist[node.first][node.second]) {
dist[neigh.first][neigh.second] = d + dist[node.first][node.second];
if (d == 1)
q.push_back(neigh);
else
q.push_front(neigh);
}
}
}
if (node.second > 0) {
neigh = node;
neigh.second--;
if (isanimal(neigh)) {
int d = calcfunc(node, neigh);
if (dist[neigh.first][neigh.second] > d + dist[node.first][node.second]) {
dist[neigh.first][neigh.second] = d + dist[node.first][node.second];
if (d == 1)
q.push_back(neigh);
else
q.push_front(neigh);
}
}
}
if (node.first < h - 1) {
neigh = node;
neigh.first++;
if (isanimal(neigh)) {
int d = calcfunc(node, neigh);
if (dist[neigh.first][neigh.second] > d + dist[node.first][node.second]) {
dist[neigh.first][neigh.second] = d + dist[node.first][node.second];
if (d == 1)
q.push_back(neigh);
else
q.push_front(neigh);
}
}
}
if (node.second < w - 1) {
neigh = node;
neigh.second++;
if (isanimal(neigh)) {
int d = calcfunc(node, neigh);
if (dist[neigh.first][neigh.second] > d + dist[node.first][node.second]) {
dist[neigh.first][neigh.second] = d + dist[node.first][node.second];
if (d == 1)
q.push_back(neigh);
else
q.push_front(neigh);
}
}
}
}
}
int main(void)
{
scanf("%d %d", &h, &w);
for (int i = 0; i < h; i++) {
getchar();
for (int j = 0; j < w; j++) {
char c = getchar();
if (c == '.')
meadow[i][j] = 0;
else if (c == 'R')
meadow[i][j] = 1;
else
meadow[i][j] = 2;
}
}
mod_dijkstra(make_pair(0,0));
printf("%d\n", ans);
return 0;
}
Compilation message
tracks.cpp: In function 'int main()':
tracks.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%d %d", &h, &w);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
8348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
436 KB |
Output is correct |
| 3 |
Correct |
1 ms |
820 KB |
Output is correct |
| 4 |
Correct |
9 ms |
7680 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4436 KB |
Output is correct |
| 6 |
Correct |
1 ms |
568 KB |
Output is correct |
| 7 |
Correct |
1 ms |
824 KB |
Output is correct |
| 8 |
Correct |
1 ms |
980 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3796 KB |
Output is correct |
| 11 |
Correct |
5 ms |
3008 KB |
Output is correct |
| 12 |
Correct |
5 ms |
4544 KB |
Output is correct |
| 13 |
Correct |
5 ms |
4436 KB |
Output is correct |
| 14 |
Correct |
4 ms |
4456 KB |
Output is correct |
| 15 |
Correct |
11 ms |
8508 KB |
Output is correct |
| 16 |
Correct |
12 ms |
8276 KB |
Output is correct |
| 17 |
Correct |
10 ms |
8116 KB |
Output is correct |
| 18 |
Correct |
8 ms |
7692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
46448 KB |
Output is correct |
| 2 |
Correct |
47 ms |
29008 KB |
Output is correct |
| 3 |
Correct |
256 ms |
147664 KB |
Output is correct |
| 4 |
Correct |
85 ms |
54912 KB |
Output is correct |
| 5 |
Correct |
180 ms |
110780 KB |
Output is correct |
| 6 |
Correct |
625 ms |
160692 KB |
Output is correct |
| 7 |
Correct |
24 ms |
48592 KB |
Output is correct |
| 8 |
Correct |
27 ms |
46348 KB |
Output is correct |
| 9 |
Correct |
2 ms |
932 KB |
Output is correct |
| 10 |
Correct |
1 ms |
576 KB |
Output is correct |
| 11 |
Correct |
25 ms |
47572 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 13 |
Correct |
45 ms |
28912 KB |
Output is correct |
| 14 |
Correct |
27 ms |
19084 KB |
Output is correct |
| 15 |
Correct |
29 ms |
21000 KB |
Output is correct |
| 16 |
Correct |
21 ms |
10752 KB |
Output is correct |
| 17 |
Correct |
112 ms |
58760 KB |
Output is correct |
| 18 |
Correct |
96 ms |
58028 KB |
Output is correct |
| 19 |
Correct |
96 ms |
54444 KB |
Output is correct |
| 20 |
Correct |
76 ms |
50332 KB |
Output is correct |
| 21 |
Correct |
162 ms |
113152 KB |
Output is correct |
| 22 |
Correct |
170 ms |
111052 KB |
Output is correct |
| 23 |
Correct |
218 ms |
92100 KB |
Output is correct |
| 24 |
Correct |
159 ms |
112080 KB |
Output is correct |
| 25 |
Correct |
473 ms |
148660 KB |
Output is correct |
| 26 |
Correct |
381 ms |
181952 KB |
Output is correct |
| 27 |
Correct |
535 ms |
177236 KB |
Output is correct |
| 28 |
Correct |
621 ms |
160676 KB |
Output is correct |
| 29 |
Correct |
621 ms |
161508 KB |
Output is correct |
| 30 |
Correct |
557 ms |
166436 KB |
Output is correct |
| 31 |
Correct |
461 ms |
117176 KB |
Output is correct |
| 32 |
Correct |
455 ms |
166784 KB |
Output is correct |
