#include <bits/stdc++.h>
using namespace std;
set<int> adj[16000000];
vector<int> topo;
int vis[16000000];
void dfs(int x){
if(vis[x])return;
vis[x]=1;
for(set<int>::iterator it=adj[x].begin();it!=adj[x].end();++it){
if(vis[(*it)])continue;
dfs(*it);
}
topo.push_back(x);
}
int main(){
int h,w;
scanf("%d%d",&h,&w);
char grid[h+5][w+5];
for(int i=0;i<h;i++){
scanf("%s",grid[i]);
}
queue<pair<int,int> > q;
int com[h][w];
memset(com,-1,sizeof(com));
int c=0;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(com[i][j]==-1){
q.push(make_pair(i,j));
com[i][j]=c;
while(!q.empty()){
pair<int,int> cur=q.front();q.pop();
for(int k=0;k<4;k++){
int nx=cur.first+dx[k],ny=cur.second+dy[k];
if(nx<0||ny<0||nx>=h||ny>=w)continue;
if(grid[nx][ny]==grid[cur.first][cur.second]&&com[nx][ny]==-1){
com[nx][ny]=c;
q.push(make_pair(nx,ny));
}
}
}
c++;
}
}
}
q.push(make_pair(0,0));
while(!q.empty()){
pair<int,int> cur=q.front();q.pop();
///printf("%d %d\n",cur.first,cur.second);
if(grid[cur.first][cur.second]=='~')continue;
for(int i=0;i<4;i++){
int nx=cur.first+dx[i],ny=cur.second+dy[i];
if(0<=nx&&nx<h&&0<=ny&&ny<w){
if(grid[nx][ny]=='~')continue;
if(grid[nx][ny]=='.'){
adj[com[cur.first][cur.second]].insert(com[nx][ny]);
continue;
}
if(grid[nx][ny]==grid[cur.first][cur.second]){
q.push(make_pair(nx,ny));
continue;
}
///printf("%d %d %d %d\n",cur.first,cur.second,nx,ny);
adj[com[cur.first][cur.second]].insert(com[nx][ny]);
q.push(make_pair(nx,ny));
}
}
grid[cur.first][cur.second]='~';
}
dfs(0);
reverse(topo.begin(),topo.end());
int dist[c]; memset(dist,-1,sizeof(dist));
dist[0]=0;
for(int i=0;i<c;i++){
int x=topo[i];
for(set<int>::iterator it=adj[x].begin();it!=adj[x].end();++it){
dist[(*it)]=max(dist[(*it)],dist[x]+1);
}
}
int ans=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(grid[i][j]=='.')ans=max(ans,dist[com[i][j]]);
}
}
printf("%d",ans);
}
Compilation message
tracks.cpp: In function 'int main()':
tracks.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&h,&w);
~~~~~^~~~~~~~~~~~~~
tracks.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",grid[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
752 ms |
758384 KB |
Output isn't correct |
| 2 |
Correct |
752 ms |
751908 KB |
Output is correct |
| 3 |
Incorrect |
681 ms |
751992 KB |
Output isn't correct |
| 4 |
Incorrect |
730 ms |
753024 KB |
Output isn't correct |
| 5 |
Incorrect |
688 ms |
753656 KB |
Output isn't correct |
| 6 |
Correct |
656 ms |
751892 KB |
Output is correct |
| 7 |
Incorrect |
667 ms |
751992 KB |
Output isn't correct |
| 8 |
Incorrect |
650 ms |
751992 KB |
Output isn't correct |
| 9 |
Incorrect |
653 ms |
752100 KB |
Output isn't correct |
| 10 |
Incorrect |
707 ms |
753388 KB |
Output isn't correct |
| 11 |
Incorrect |
686 ms |
752236 KB |
Output isn't correct |
| 12 |
Incorrect |
739 ms |
754440 KB |
Output isn't correct |
| 13 |
Incorrect |
741 ms |
753596 KB |
Output isn't correct |
| 14 |
Incorrect |
666 ms |
753592 KB |
Output isn't correct |
| 15 |
Incorrect |
815 ms |
758236 KB |
Output isn't correct |
| 16 |
Incorrect |
756 ms |
758192 KB |
Output isn't correct |
| 17 |
Incorrect |
760 ms |
759288 KB |
Output isn't correct |
| 18 |
Incorrect |
713 ms |
753016 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
719 ms |
753076 KB |
Output is correct |
| 2 |
Incorrect |
1004 ms |
787532 KB |
Output isn't correct |
| 3 |
Execution timed out |
2088 ms |
973368 KB |
Time limit exceeded |
| 4 |
Incorrect |
1297 ms |
810412 KB |
Output isn't correct |
| 5 |
Runtime error |
1346 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Execution timed out |
2106 ms |
849140 KB |
Time limit exceeded |
| 7 |
Correct |
719 ms |
753084 KB |
Output is correct |
| 8 |
Correct |
687 ms |
753048 KB |
Output is correct |
| 9 |
Incorrect |
717 ms |
753112 KB |
Output isn't correct |
| 10 |
Correct |
679 ms |
752508 KB |
Output is correct |
| 11 |
Correct |
705 ms |
752504 KB |
Output is correct |
| 12 |
Correct |
749 ms |
753888 KB |
Output is correct |
| 13 |
Incorrect |
1042 ms |
787556 KB |
Output isn't correct |
| 14 |
Incorrect |
887 ms |
772596 KB |
Output isn't correct |
| 15 |
Correct |
977 ms |
782064 KB |
Output is correct |
| 16 |
Incorrect |
858 ms |
767564 KB |
Output isn't correct |
| 17 |
Incorrect |
1615 ms |
844324 KB |
Output isn't correct |
| 18 |
Correct |
1568 ms |
875712 KB |
Output is correct |
| 19 |
Incorrect |
1285 ms |
811332 KB |
Output isn't correct |
| 20 |
Incorrect |
1026 ms |
812784 KB |
Output isn't correct |
| 21 |
Incorrect |
1786 ms |
909904 KB |
Output isn't correct |
| 22 |
Runtime error |
1294 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 23 |
Execution timed out |
2110 ms |
924460 KB |
Time limit exceeded |
| 24 |
Runtime error |
1654 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 25 |
Execution timed out |
2101 ms |
906596 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2091 ms |
814324 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2079 ms |
833580 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2114 ms |
852172 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2083 ms |
843028 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2111 ms |
843132 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2103 ms |
872556 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2094 ms |
849256 KB |
Time limit exceeded |
