# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22721 | past future present (#40) | Young Zebra (KRIII5_YZ) | C++14 | 406 ms | 88352 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<stdio.h>
#include<vector>
#include<queue>
using namespace std;
char in[405];
bool fl[1200][1200];
int dx[4] = { -1,0,0,1 }, dy[4] = { 0,1,-1,0 }, n, m, nn, mm;
vector<int> g[1200 * 1200];
int ans[400 * 400], v[1200][1200], nf;
inline int pti(int y, int x)
{
return y*mm + x;
}
int foo(int i, int j)
{
if (v[i][j] != 0) return ans[v[i][j]];
nf++;
v[i][j] = nf;
queue<int> q;
q.emplace(pti(i, j));
while (!q.empty())
{
int idx = q.front();
int y = idx / mm;
int x = idx % mm;
q.pop();
if(ans[nf]>=0) ans[nf]++;
for (int e : g[idx])
{
int yy = e / mm, xx = e%mm;
if ((yy + n == i || i + n == yy) && (xx + m == j || j + m == xx))
{
ans[nf] = -1;
}
if (v[yy][xx]) continue;
v[yy][xx] = nf;
q.emplace(e);
}
}
return ans[nf];
}
int main()
{
scanf("%d%d", &n, &m);
nn = n * 3;
mm = m * 3;
for(int i=0;i<n;i++)
{
scanf("%s", in);
for (int j = 0; j < m; j++)
{
fl[i][j] = fl[i][j + m] = fl[i][j + 2 * m] = in[j] == 'B';
fl[i + n][j] = fl[i + n][j + m] = fl[i + n][j + 2 * m] = in[j] == 'B';
fl[i + n * 2][j] = fl[i + n * 2][j + m] = fl[i + n * 2][j + 2 * m] = in[j] == 'B';
}
}
for(int i=0;i<nn;i++)
for (int j = 0; j < mm; j++)
{
int p1 = pti(i, j);
for (int d = 0; d < 4; d++)
{
int x = j + dx[d], y = i + dy[d];
if (x < 0 || x >= 3 * m || y < 0 || y >= 3 * n) continue;
if (fl[i][j] != fl[y][x]) continue;
int p2 = pti(y, x);
g[p1].push_back(p2);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
printf("%d ", foo(i+n, j+m));
}
puts("");
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |