# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22433 | 카시코이 (#40) | Young Zebra (KRIII5_YZ) | C++14 | 96 ms | 19468 KiB |
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 <cstdio>
#include <vector>
#include <queue>
#include <unordered_set>
#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 outlist[3000000];
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;
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;
}
}
unordered_set<int> edgeset;
for (int i = 0; i < n * 3; ++i) {
edgeset.insert(visit[i][0]);
edgeset.insert(visit[i][m * 3 - 1]);
}
for (int j = 0; j < m * 3; ++j) {
edgeset.insert(visit[0][j]);
edgeset.insert(visit[n * 3 - 1][j]);
}
/*
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) {
int out = outlist[visit[i][j]];
if (edgeset.count(visit[i][j])) out = -1;
printf("%d", out);
if (j < m * 2 - 1) putchar(' ');
}
putchar('\n');
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |