#include <bits/stdc++.h>
using namespace std;
int H, W;
int grid[4001][4001], cc[4001][4001];
queue<pair<int,int>> q;
vector<pair<int,int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void ff(int cur, int val){
while(!q.empty()){
auto temp = q.front();
int x = temp.first, y = temp.second;
q.pop();
for(auto [dx, dy] : dir){
if((x+dx > -1)&& (x+dx < H) && (y+dy > -1) && (y+dy < W) && (cc[x+dx][y+dy] == -1) && (grid[x+dx][y+dy] == cur)){
cc[x+dx][y+dy] = val;
q.push({x+dx, y+dy});
}
}
}
}
int main(){
cin>>H>>W;
memset(grid, 0, sizeof(grid));
memset(cc, -1, sizeof(cc));
for(int i = 0; i < H; i++){
string s; cin>>s;
for(int j = 0; j < W; j++){
if(s[j] == 'F') grid[i][j] = 1;
else if(s[j] == 'R') grid[i][j] = 2;
}
}
int val = 0;
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
if(cc[i][j] == -1 && grid[i][j] != 0){
cc[i][j] = val;
q.push({i,j});
ff(grid[i][j], val);
val++;
}
}
}
vector<set<int>> adj(val+1);
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
if(grid[i][j] != 0){
for(auto [dx, dy] : dir){
if(i+dx > -1 && i+dx < H && j+dy > -1 && j+dy < W && cc[i+dx][j+dy] != cc[i][j] && cc[i+dx][j+dy] != -1){
adj[cc[i][j]].insert(cc[i+dx][j+dy]);
adj[cc[i+dx][j+dy]].insert(cc[i][j]);
}
}
}
}
}
queue<int> q1;
q1.push(0);
vector<int> d(val+1, -1);
int ans = 0;
while(!q1.empty()){
auto temp = q1.front();
q1.pop();
for(auto i : adj[temp]){
if(d[i] == -1){
q1.push(i);
d[i] = d[temp] + 1;
ans = max(ans, d[i]);
}
}
}
cout<<ans+1<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
132612 KB |
Output isn't correct |
| 2 |
Incorrect |
53 ms |
125528 KB |
Output isn't correct |
| 3 |
Incorrect |
45 ms |
125788 KB |
Output isn't correct |
| 4 |
Incorrect |
55 ms |
126032 KB |
Output isn't correct |
| 5 |
Incorrect |
57 ms |
126800 KB |
Output isn't correct |
| 6 |
Incorrect |
45 ms |
125520 KB |
Output isn't correct |
| 7 |
Incorrect |
45 ms |
125532 KB |
Output isn't correct |
| 8 |
Incorrect |
48 ms |
125788 KB |
Output isn't correct |
| 9 |
Incorrect |
44 ms |
125776 KB |
Output isn't correct |
| 10 |
Incorrect |
55 ms |
126904 KB |
Output isn't correct |
| 11 |
Incorrect |
53 ms |
125768 KB |
Output isn't correct |
| 12 |
Incorrect |
64 ms |
128140 KB |
Output isn't correct |
| 13 |
Incorrect |
65 ms |
126768 KB |
Output isn't correct |
| 14 |
Incorrect |
48 ms |
126804 KB |
Output isn't correct |
| 15 |
Incorrect |
79 ms |
132176 KB |
Output isn't correct |
| 16 |
Incorrect |
95 ms |
132452 KB |
Output isn't correct |
| 17 |
Incorrect |
68 ms |
131664 KB |
Output isn't correct |
| 18 |
Incorrect |
59 ms |
126032 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
126288 KB |
Output isn't correct |
| 2 |
Incorrect |
162 ms |
157456 KB |
Output isn't correct |
| 3 |
Incorrect |
729 ms |
347940 KB |
Output isn't correct |
| 4 |
Incorrect |
217 ms |
164784 KB |
Output isn't correct |
| 5 |
Incorrect |
820 ms |
776224 KB |
Output isn't correct |
| 6 |
Incorrect |
1635 ms |
207140 KB |
Output isn't correct |
| 7 |
Incorrect |
56 ms |
126348 KB |
Output isn't correct |
| 8 |
Incorrect |
59 ms |
126292 KB |
Output isn't correct |
| 9 |
Incorrect |
58 ms |
126700 KB |
Output isn't correct |
| 10 |
Incorrect |
59 ms |
126036 KB |
Output isn't correct |
| 11 |
Incorrect |
57 ms |
125880 KB |
Output isn't correct |
| 12 |
Incorrect |
62 ms |
127292 KB |
Output isn't correct |
| 13 |
Incorrect |
179 ms |
158548 KB |
Output isn't correct |
| 14 |
Incorrect |
122 ms |
145004 KB |
Output isn't correct |
| 15 |
Incorrect |
121 ms |
146904 KB |
Output isn't correct |
| 16 |
Incorrect |
139 ms |
141140 KB |
Output isn't correct |
| 17 |
Incorrect |
350 ms |
210684 KB |
Output isn't correct |
| 18 |
Incorrect |
326 ms |
207696 KB |
Output isn't correct |
| 19 |
Incorrect |
291 ms |
166996 KB |
Output isn't correct |
| 20 |
Incorrect |
214 ms |
178324 KB |
Output isn't correct |
| 21 |
Incorrect |
461 ms |
263748 KB |
Output isn't correct |
| 22 |
Incorrect |
876 ms |
781012 KB |
Output isn't correct |
| 23 |
Incorrect |
665 ms |
290192 KB |
Output isn't correct |
| 24 |
Incorrect |
501 ms |
347352 KB |
Output isn't correct |
| 25 |
Incorrect |
1383 ms |
463956 KB |
Output isn't correct |
| 26 |
Correct |
518 ms |
131920 KB |
Output is correct |
| 27 |
Incorrect |
755 ms |
136504 KB |
Output isn't correct |
| 28 |
Incorrect |
1716 ms |
215584 KB |
Output isn't correct |
| 29 |
Incorrect |
1500 ms |
181988 KB |
Output isn't correct |
| 30 |
Incorrect |
1212 ms |
168116 KB |
Output isn't correct |
| 31 |
Execution timed out |
2027 ms |
416804 KB |
Time limit exceeded |
| 32 |
Incorrect |
701 ms |
153980 KB |
Output isn't correct |
