// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
const int mx = 4005;
char a[mx][mx];
deque<pair<int,int>>ok;
int dist[mx][mx];
//0/1 dfs, i do not understand the question lol. If both R and F, are in the graph obviously, the minimum amount of animals is 2.
//no ?
// if there is an appearance of 1, then its just 1.
//otherwise 0.
//How could they be more?
//THe above thought is debunked, upon looking at setups impossible.
//I was just thinking of the cases where the minimum was indeed 2, but that is not always the case.1
//if its the same track we want to visit it and clear it all before going to differing tracks.
int h,w;
bool ontrack(int x, int y ){
return (x>=1)&&(y>=1)&&(x<=h)&&(y<=w)&&(a[x][y]!='.');
}
int main() {
cin>>h>>w;
for(int i=1;i<=h;i++){
string s;
cin>>s;
for(int j=1;j<=w;j++){
char g = s[j-1];
a[i][j]=g;
dist[i][j]=0;
}
}
int ans = INT_MIN;
ok.push_front({1,1});
dist[1][1]=1;
while(!ok.empty()){
int x = ok.front().first;
int y = ok.front().second;
ok.pop_front();
ans = max(ans, dist[x][y]);
//consider up down left right
for(int i = -1;i<=1;i+=2){
int nx = x + i;
if(ontrack(nx,y)&&dist[nx][y]==0){
//depth[x][y]==0 means not visited.
//push the same tracks to priority.
//to commit some sort of flood fill.
if(a[x][y]==a[nx][y]){
//same track/
ok.push_front({nx,y});
dist[nx][y]=dist[x][y];
}else{
ok.push_back({nx,y});
dist[nx][y]=dist[x][y]+1;
}
}
}
for(int i=-1;i<=1;i+=2){
int ny=y+i;
if(ontrack(x,ny)&&dist[x][ny]==0){
//dist[x][y]==0 means not visited.
if(a[x][y]==a[x][ny]){
//same track/'
ok.push_front({x,ny});
dist[x][ny]=dist[x][y];
}else{
ok.push_back({x,ny});
//wait until all the last animals track connected components, are done running.
//then this is as if the next layer of a bipartite tree.
dist[x][ny]=dist[x][y]+1;
}
}
}
}
cout<<ans<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
7 ms |
13148 KB |
Output is correct |
| 5 |
Correct |
4 ms |
10840 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4552 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6488 KB |
Output is correct |
| 11 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
5 ms |
10844 KB |
Output is correct |
| 13 |
Correct |
4 ms |
10844 KB |
Output is correct |
| 14 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 15 |
Correct |
10 ms |
12892 KB |
Output is correct |
| 16 |
Correct |
11 ms |
12892 KB |
Output is correct |
| 17 |
Correct |
9 ms |
12892 KB |
Output is correct |
| 18 |
Correct |
7 ms |
13184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
78428 KB |
Output is correct |
| 2 |
Correct |
44 ms |
28724 KB |
Output is correct |
| 3 |
Correct |
322 ms |
94436 KB |
Output is correct |
| 4 |
Correct |
83 ms |
45192 KB |
Output is correct |
| 5 |
Correct |
207 ms |
70996 KB |
Output is correct |
| 6 |
Correct |
614 ms |
107740 KB |
Output is correct |
| 7 |
Correct |
10 ms |
78684 KB |
Output is correct |
| 8 |
Correct |
12 ms |
78428 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 11 |
Correct |
10 ms |
78416 KB |
Output is correct |
| 12 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
44 ms |
28508 KB |
Output is correct |
| 14 |
Correct |
25 ms |
21852 KB |
Output is correct |
| 15 |
Correct |
26 ms |
23900 KB |
Output is correct |
| 16 |
Correct |
20 ms |
11356 KB |
Output is correct |
| 17 |
Correct |
110 ms |
47576 KB |
Output is correct |
| 18 |
Correct |
99 ms |
47444 KB |
Output is correct |
| 19 |
Correct |
86 ms |
45136 KB |
Output is correct |
| 20 |
Correct |
74 ms |
40788 KB |
Output is correct |
| 21 |
Correct |
193 ms |
73316 KB |
Output is correct |
| 22 |
Correct |
214 ms |
70956 KB |
Output is correct |
| 23 |
Correct |
203 ms |
61536 KB |
Output is correct |
| 24 |
Correct |
198 ms |
73040 KB |
Output is correct |
| 25 |
Correct |
496 ms |
94544 KB |
Output is correct |
| 26 |
Correct |
433 ms |
134484 KB |
Output is correct |
| 27 |
Correct |
560 ms |
112020 KB |
Output is correct |
| 28 |
Correct |
643 ms |
108124 KB |
Output is correct |
| 29 |
Correct |
650 ms |
107908 KB |
Output is correct |
| 30 |
Correct |
570 ms |
108292 KB |
Output is correct |
| 31 |
Correct |
412 ms |
76704 KB |
Output is correct |
| 32 |
Correct |
506 ms |
109804 KB |
Output is correct |
