#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
char board[403][403];
int visit[1203][1203];
int di[] = { 0, 1, 0, -1 }, dj[] = { 1, 0, -1, 0 };
int out[403][403];
int outlist[1500000];
struct DJSet {
vector<int> par, rank;
int setCnt;
DJSet(int _sz) : par(_sz), rank(_sz), setCnt(0) {
init();
}
void init() {
setCnt = par.size();
for (int i = 0; i < par.size(); ++i) par[i] = i;
fill(rank.begin(), rank.end(), 0);
}
int find(int p) {
return p == par[p] ? p : (par[p] = find(par[p]));
}
bool merge(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (rank[a] > rank[b]) swap(a, b);
par[a] = b;
if (rank[a] == rank[b]) rank[b] += 1;
--setCnt;
return true;
}
};
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%s", board[i]);
}
int cur = 0;
for (int i = 0; i < 3 * n; ++i) {
for (int j = 0; j < 3 * m; ++j) {
if (visit[i][j]) continue;
++cur;
int cnt = 0;
bool ok = true;
queue<pair<int, int>> q;
visit[i][j] = cur;
q.emplace(i, j);
while (!q.empty()) {
int ci = q.front().first, cj = q.front().second;
q.pop();
++cnt;
for (int k = 0; k < 4; ++k) {
int ni = ci + di[k], nj = cj + dj[k];
if (ni < 0 || ni >= n * 3 || nj < 0 || nj >= m * 3 || visit[ni][nj]) continue;
if (board[ni % n][nj % m] != board[i % n][j % m]) continue;
visit[ni][nj] = cur;
q.emplace(ni, nj);
}
}
outlist[cur] = cnt;
}
}
DJSet dj(cur + 2);
for (int i = 0; i < n * 3; ++i) {
if (visit[i][0] == 0 || visit[i][m * 3 - 1] == 0) continue;
if (board[i][0] == board[i][m - 1])
dj.merge(visit[i][0], visit[i][m * 3 - 1]);
}
for (int j = 0; j < m * 3; ++j) {
if (visit[0][j] == 0 || visit[n * 3 - 1][j] == 0) continue;
if (board[0][j] == board[n - 1][j])
dj.merge(visit[0][j], visit[n * 3 - 1][j]);
}
for (int i = n; i < n * 2; ++i) {
for (int j = m; j < m * 2; ++j) {
printf("%d ", outlist[visit[i][j]]);
}
putchar('\n');
}
return 0;
}
Compilation message
YZ.cpp: In member function 'void DJSet::init()':
YZ.cpp:23:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < par.size(); ++i) par[i] = i;
^
YZ.cpp: In function 'int main()':
YZ.cpp:55:9: warning: unused variable 'ok' [-Wunused-variable]
bool ok = true;
^
YZ.cpp:42:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
^
YZ.cpp:44:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", board[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
14240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
