This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define MAX 4010
using namespace std;
typedef pair<int,int> pii;
int dx[] = {0 , 0 , 1 , -1};
int dy[] = {1 , -1 , 0 , 0};
int n, m;
int curNode;
int node[MAX][MAX];
int dist[MAX*MAX];
bool marc[MAX][MAX];
bool marcBFS[MAX*MAX];
pii cell[MAX*MAX];
char v[MAX][MAX];
//vector<int> dist;
//vector<bool> marcBFS;
//vector<pii> cell;
queue<int> q;
bool check(int i, int j)
{
if(i <= 0 || j <= 0) return false;
if(i > n || j > m) return false;
return true;
}
void DFS(int i, int j)//ESTOU PEGANDO TODOS COM V
{
marc[i][j] = true;
for(int g = 0 ; g < 4 ; g++)
{
int ni = i + dx[g];
int nj = j + dy[g];
if(!check(ni , nj)) continue;
if(marc[ni][nj]) continue;
if(v[ni][nj] != v[i][j]) continue;
node[ni][nj] = node[i][j];
DFS(ni , nj);
}
}
void DFSMake(int i, int j)
{
marc[i][j] = true;
for(int g = 0 ; g < 4 ; g++)
{
int ni = i + dx[g];
int nj = j + dy[g];
//printf("%d %d %d %d\n",i,j,ni,nj);
if(!check(ni , nj)) continue;
//printf("i = %d %d %d %d\n",i,j,ni,nj);
if(marc[ni][nj]) continue;
//printf("i = %d j = %d ni = %d nj = %d\n",i,j,ni,nj);
if(v[ni][nj] == '.') continue;
if(v[ni][nj] != v[i][j] && !marcBFS[ node[ni][nj] ])
{
if(!marcBFS[ node[ni][nj] ])
{
q.push( node[ni][nj] );
marcBFS[ node[ni][nj] ] = true;
dist[ node[ni][nj] ] = dist[ node[i][j] ] + 1;
}
//printf("i = %d j = %d %d %d\n",i,j,ni,nj);
continue;
}
if(v[ni][nj] != v[i][j]) continue;
DFSMake(ni , nj);
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int g = 1 ; g <= n ; g++)
for(int h = 1 ; h <= m ; h++)
scanf(" %c",&v[g][h]);
for(int g = 1 ; g <= n ; g++)
{
for(int h = 1 ; h <= m ; h++)
{
if(marc[g][h]) continue;
if(v[g][h] == '.') continue;
node[g][h] = curNode++;//CURNODE N EXISTE
//printf("g = %d h = %d %d\n",g,h,curNode - 1) ;
//dist.push_back( 0 );
cell[curNode - 1] = {g , h};
//cell.push_back({g , h});
//marcBFS.push_back(false);
DFS(g , h);
}
}
memset(marc , false , sizeof(marc));
marcBFS[0] = true;
q.push(0);
while( !q.empty() )
{
int cur = q.front(); q.pop();
int i = cell[cur].first;
int j = cell[cur].second;
DFSMake(i , j);
}
int ans = 0;
for(int g = 0 ; g < curNode ; g++)
ans = max(ans , dist[g]);
printf("%d\n",ans + 1);
}
Compilation message (stderr)
tracks.cpp: In function 'int main()':
tracks.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
tracks.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&v[g][h]);
~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |