#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int pole[4004][4004];
int dist[4004][4004];
bool vis[4004][4004];
int k_x[4]={-1,0,1,0};
int k_y[4]={0,-1,0,1};
deque<pii> dq;
int bfs01(){
int mx=0;
dq.push_back({1,1});
dist[1][1]=1;
vis[1][1]=true;
while(dq.size()){
pii now=dq.front();
dq.pop_front();
mx=max(mx,dist[now.first][now.second]);
for (int i = 0; i<4; i++){
if (pole[now.first+k_x[i]][now.second+k_y[i]] && !vis[now.first+k_x[i]][now.second+k_y[i]]){
if (pole[now.first+k_x[i]][now.second+k_y[i]]==pole[now.first][now.second]){
dist[now.first+k_x[i]][now.second+k_y[i]]=dist[now.first][now.second];
dq.push_front({now.first+k_x[i],now.second+k_y[i]});
}
else{
dist[now.first+k_x[i]][now.second+k_y[i]]=dist[now.first][now.second]+1;
dq.push_back({now.first+k_x[i],now.second+k_y[i]});
}
vis[now.first+k_x[i]][now.second+k_y[i]]=true;
}
}
}
return mx;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
char zn;
for (int i = 1; i<=n; i++){
for (int j = 1; j<=m; j++){
cin >> zn;
if (zn=='R')pole[i][j]=1;
if (zn=='F')pole[i][j]=2;
}
}
cout << bfs01() << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
21340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
11 ms |
21156 KB |
Output is correct |
| 5 |
Correct |
4 ms |
13916 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4556 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 9 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 10 |
Correct |
4 ms |
13660 KB |
Output is correct |
| 11 |
Correct |
3 ms |
11612 KB |
Output is correct |
| 12 |
Correct |
6 ms |
13916 KB |
Output is correct |
| 13 |
Correct |
5 ms |
13912 KB |
Output is correct |
| 14 |
Correct |
4 ms |
13912 KB |
Output is correct |
| 15 |
Correct |
12 ms |
21168 KB |
Output is correct |
| 16 |
Correct |
14 ms |
21236 KB |
Output is correct |
| 17 |
Correct |
11 ms |
20828 KB |
Output is correct |
| 18 |
Correct |
8 ms |
21084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
88908 KB |
Output is correct |
| 2 |
Correct |
48 ms |
49756 KB |
Output is correct |
| 3 |
Correct |
273 ms |
131176 KB |
Output is correct |
| 4 |
Correct |
84 ms |
71688 KB |
Output is correct |
| 5 |
Correct |
175 ms |
105300 KB |
Output is correct |
| 6 |
Correct |
585 ms |
167540 KB |
Output is correct |
| 7 |
Correct |
21 ms |
90972 KB |
Output is correct |
| 8 |
Correct |
19 ms |
88924 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
19 ms |
87128 KB |
Output is correct |
| 12 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 13 |
Correct |
45 ms |
49756 KB |
Output is correct |
| 14 |
Correct |
27 ms |
37724 KB |
Output is correct |
| 15 |
Correct |
28 ms |
40020 KB |
Output is correct |
| 16 |
Correct |
20 ms |
19036 KB |
Output is correct |
| 17 |
Correct |
113 ms |
71424 KB |
Output is correct |
| 18 |
Correct |
101 ms |
73800 KB |
Output is correct |
| 19 |
Correct |
92 ms |
70996 KB |
Output is correct |
| 20 |
Correct |
67 ms |
66772 KB |
Output is correct |
| 21 |
Correct |
169 ms |
101976 KB |
Output is correct |
| 22 |
Correct |
174 ms |
103400 KB |
Output is correct |
| 23 |
Correct |
238 ms |
89492 KB |
Output is correct |
| 24 |
Correct |
167 ms |
100432 KB |
Output is correct |
| 25 |
Correct |
538 ms |
153688 KB |
Output is correct |
| 26 |
Correct |
298 ms |
183648 KB |
Output is correct |
| 27 |
Correct |
421 ms |
182404 KB |
Output is correct |
| 28 |
Correct |
556 ms |
167372 KB |
Output is correct |
| 29 |
Correct |
558 ms |
168164 KB |
Output is correct |
| 30 |
Correct |
503 ms |
171280 KB |
Output is correct |
| 31 |
Correct |
450 ms |
123912 KB |
Output is correct |
| 32 |
Correct |
395 ms |
171224 KB |
Output is correct |
