# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22457 | 카시코이 (#40) | Young Zebra (KRIII5_YZ) | C++98 | 66 ms | 53544 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 <set>
#include <algorithm>
using namespace std;
int n, m;
char board[1603][1603];
int visit[1603][1603];
int di[] = { 0, 1, 0, -1 }, dj[] = { 1, 0, -1, 0 };
int outlist[10000000];
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%s", board[i]);
}
for (int i = n; i < n * 3; ++i) {
for (int j = m; j < m * 3; ++j) {
board[i][j] = board[i % n][j % m];
}
}
int cur = 0;
for (int i = 0; i < 3 * n; ++i) {
for (int j = 0; j < 3 * m; ++j) {
if (visit[i][j] != 0) continue;
char base = board[i][j];
++cur;
int cnt = 0;
queue<pair<int, int> > q;
visit[i][j] = cur;
q.push(make_pair(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] != 0) continue;
if (board[ni][nj] != base) continue;
visit[ni][nj] = cur;
q.push(make_pair(ni, nj));
}
}
outlist[cur] = cnt;
}
}
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 = n; i < n * 2; ++i) {
for (int j = m; j < m * 2; ++j) {
int out = outlist[visit[i][j]];
if (edgeset.find(visit[i][j]) != edgeset.end()) out = -1;
printf("%d", out);
if (j < m * 2 - 1) printf(" ");
}
printf("\n");
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |