#include <bits/stdc++.h>
#define N 4001
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, m, ans, cnt, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int id[N][N], pai[N*N], dist[N*N];
bool ok[N][N], Fill[N*N];
char mat[N][N], T;
vector<int> grafo[N*N];
inline void bfs(int x, int y, int &p)
{
queue< pii > fila;
fila.push({x, y});
while(!fila.empty())
{
int x = fila.front().f, y = fila.front().s;
fila.pop();
ok[x][y] = 1;
pai[id[x][y]] = p;
for(int pp = 0; pp < 4; pp++)
{
int a = x + dx[pp], b = y + dy[pp];
if(!a or !b or a > n or b > m or mat[a][b] != mat[x][y] or ok[a][b]) continue;
ok[a][b] = 1;
fila.push({a, b});
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin>>mat[i][j];
id[i][j] = ++cnt;
pai[id[i][j]] = id[i][j];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(mat[i][j] == '.' or ok[i][j]) continue;
bfs(i, j, id[i][j]);
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(mat[i][j] == '.') continue;
if(Fill[pai[id[i][j]]]) continue;
Fill[pai[id[i][j]]] = 1;
for(int p = 0; p < 4; p++)
{
int a = i + dx[p], b = j + dy[p];
if(!a or !b or a > n or b > m) continue;
if(mat[a][b] != mat[i][j] and mat[a][b] != '.')
{
int u = pai[id[a][b]], v = pai[id[i][j]];
grafo[v].push_back(u);
}
}
}
}
queue<int> fila;
dist[pai[id[1][1]]] = 1;
fila.push(pai[id[1][1]]);
while(!fila.empty())
{
int x = fila.front();
ans = max(ans, dist[x]);
fila.pop();
for(auto v: grafo[x])
{
if(dist[v] == 0)
{
dist[v] = dist[x] + 1;
fila.push(v);
}
}
}
cout<<ans<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
340 ms |
385272 KB |
Output isn't correct |
| 2 |
Incorrect |
307 ms |
385272 KB |
Output isn't correct |
| 3 |
Incorrect |
300 ms |
385272 KB |
Output isn't correct |
| 4 |
Incorrect |
336 ms |
385272 KB |
Output isn't correct |
| 5 |
Incorrect |
334 ms |
385272 KB |
Output isn't correct |
| 6 |
Incorrect |
309 ms |
385272 KB |
Output isn't correct |
| 7 |
Incorrect |
307 ms |
385272 KB |
Output isn't correct |
| 8 |
Incorrect |
327 ms |
385272 KB |
Output isn't correct |
| 9 |
Incorrect |
312 ms |
385272 KB |
Output isn't correct |
| 10 |
Incorrect |
317 ms |
385272 KB |
Output isn't correct |
| 11 |
Incorrect |
329 ms |
385272 KB |
Output isn't correct |
| 12 |
Incorrect |
328 ms |
385272 KB |
Output isn't correct |
| 13 |
Incorrect |
318 ms |
385272 KB |
Output isn't correct |
| 14 |
Incorrect |
347 ms |
385272 KB |
Output isn't correct |
| 15 |
Incorrect |
399 ms |
385836 KB |
Output isn't correct |
| 16 |
Incorrect |
405 ms |
385836 KB |
Output isn't correct |
| 17 |
Incorrect |
364 ms |
385836 KB |
Output isn't correct |
| 18 |
Incorrect |
338 ms |
385836 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
373 ms |
422356 KB |
Output isn't correct |
| 2 |
Incorrect |
458 ms |
422356 KB |
Output isn't correct |
| 3 |
Incorrect |
1432 ms |
593800 KB |
Output isn't correct |
| 4 |
Incorrect |
625 ms |
593800 KB |
Output isn't correct |
| 5 |
Execution timed out |
2114 ms |
631816 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2085 ms |
631816 KB |
Time limit exceeded |
| 7 |
Incorrect |
398 ms |
631816 KB |
Output isn't correct |
| 8 |
Incorrect |
379 ms |
631816 KB |
Output isn't correct |
| 9 |
Incorrect |
315 ms |
631816 KB |
Output isn't correct |
| 10 |
Incorrect |
312 ms |
631816 KB |
Output isn't correct |
| 11 |
Incorrect |
383 ms |
631816 KB |
Output isn't correct |
| 12 |
Incorrect |
346 ms |
631816 KB |
Output isn't correct |
| 13 |
Incorrect |
481 ms |
631816 KB |
Output isn't correct |
| 14 |
Incorrect |
434 ms |
631816 KB |
Output isn't correct |
| 15 |
Incorrect |
468 ms |
631816 KB |
Output isn't correct |
| 16 |
Incorrect |
428 ms |
631816 KB |
Output isn't correct |
| 17 |
Incorrect |
741 ms |
631816 KB |
Output isn't correct |
| 18 |
Incorrect |
753 ms |
631816 KB |
Output isn't correct |
| 19 |
Incorrect |
607 ms |
631816 KB |
Output isn't correct |
| 20 |
Incorrect |
567 ms |
631816 KB |
Output isn't correct |
| 21 |
Incorrect |
956 ms |
631816 KB |
Output isn't correct |
| 22 |
Execution timed out |
2051 ms |
631816 KB |
Time limit exceeded |
| 23 |
Incorrect |
1179 ms |
631816 KB |
Output isn't correct |
| 24 |
Incorrect |
1257 ms |
631816 KB |
Output isn't correct |
| 25 |
Execution timed out |
2013 ms |
631816 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2100 ms |
631816 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2074 ms |
631816 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2092 ms |
631816 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2027 ms |
631816 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2107 ms |
631816 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2028 ms |
631816 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2095 ms |
631816 KB |
Time limit exceeded |
