#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int comp[4001][4001];
char arr[4001][4001];
int n, m;
bool check (int i, int j) {
return (i >= 1 && i <= n && j >= 1 && j <= m && arr[i][j] != '.');
}
void dfs (int i, int j) {
for (int l = 0; l < 4; l++) {
if (check(i + dx[l], j + dy[l]) && comp[i + dx[l]][j + dy[l]] == 0 && arr[i + dx[l]][j + dy[l]] == arr[i][j]) {
comp[i + dx[l]][j + dy[l]] = comp[i][j];
dfs(i + dx[l], j + dy[l]);
}
}
}
queue <int> adj[16000001];
bool vis[16000001];
signed main () {
ios::sync_with_stdio(0); cin.tie(0);
memset(vis, false, sizeof(vis));
cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> arr[i][j];
int c = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (comp[i][j] == 0 && arr[i][j] != '.') {
c++;
comp[i][j] = c;
dfs(i, j);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (arr[i][j] == '.') continue;
for (int l = 0; l < 4; l++) {
if (check(i + dx[l], j + dy[l])) {
if (comp[i + dx[l]][j + dy[l]] != comp[i][j]) {
adj[comp[i][j]].push(comp[i + dx[l]][j + dy[l]]);
adj[comp[i + dx[l]][j + dy[l]]].push(comp[i][j]);
}
}
}
}
}
queue <int> cur;
cur.push(comp[1][1]); vis[comp[1][1]] = 1;
int cnt = 1;
int ans = 0;
while (!cur.empty()) {
auto u = cur.size(); while (u--) {
int k = cur.front(); cur.pop();
ans = cnt;
while (!adj[k].empty()) {
int j = adj[k].front();
adj[k].pop();
if (!vis[j]) {
vis[j] = 1; cur.push(j);
}
}
}
cnt++;
}
cout << ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
396 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
373 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
382 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
385 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
375 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
449 ms |
1048576 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
369 ms |
1048576 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
399 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
381 ms |
1048576 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
358 ms |
1048576 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
374 ms |
1048576 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
370 ms |
1048576 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
380 ms |
1048576 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
410 ms |
1048576 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
411 ms |
1048576 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
362 ms |
1048576 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
372 ms |
1048576 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
360 ms |
1048576 KB |
Execution killed with signal 9 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
374 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
384 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
390 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
376 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
399 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
405 ms |
1048576 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
359 ms |
1048576 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
374 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
358 ms |
1048576 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
363 ms |
1048576 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
372 ms |
1048576 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
372 ms |
1048576 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
361 ms |
1048576 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
507 ms |
1048576 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
399 ms |
1048576 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
357 ms |
1048576 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
369 ms |
1048576 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
383 ms |
1048576 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
382 ms |
1048576 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
380 ms |
1048576 KB |
Execution killed with signal 9 |
| 21 |
Runtime error |
380 ms |
1048576 KB |
Execution killed with signal 9 |
| 22 |
Runtime error |
386 ms |
1048576 KB |
Execution killed with signal 9 |
| 23 |
Runtime error |
367 ms |
1048576 KB |
Execution killed with signal 9 |
| 24 |
Runtime error |
368 ms |
1048576 KB |
Execution killed with signal 9 |
| 25 |
Runtime error |
386 ms |
1048576 KB |
Execution killed with signal 9 |
| 26 |
Runtime error |
363 ms |
1048576 KB |
Execution killed with signal 9 |
| 27 |
Runtime error |
372 ms |
1048576 KB |
Execution killed with signal 9 |
| 28 |
Runtime error |
371 ms |
1048576 KB |
Execution killed with signal 9 |
| 29 |
Runtime error |
390 ms |
1048576 KB |
Execution killed with signal 9 |
| 30 |
Runtime error |
378 ms |
1048576 KB |
Execution killed with signal 9 |
| 31 |
Runtime error |
376 ms |
1048576 KB |
Execution killed with signal 9 |
| 32 |
Runtime error |
363 ms |
1048576 KB |
Execution killed with signal 9 |
