# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22715 | dried chocochip on Daegu asphalt (#40) | Young Zebra (KRIII5_YZ) | C++11 | 500 ms | 165112 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<bits/stdc++.h>
using namespace std;
int n, m;
char mmap[400][400];
int cc[400][400], c_idx;
bool visited[400][400];
int cc_sz[400*400+2];
int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};
char mmap2[2800][2800];
int cc2[2800][2800], c_idx2;
bool visited2[2800][2800];
void dfs2(int i, int j)
{
visited2[i][j] = true;
cc2[i][j] = c_idx2;
for(int k = 0; k < 4; k++)
{
int ni = i+di[k], nj = j+dj[k];
if(ni < 0 || ni >= 7*n || nj < 0 || nj >= 7*m) continue;
if(!visited2[ni][nj] && mmap2[i][j] == mmap2[ni][nj])
dfs2(ni, nj);
}
}
void dfs(int i, int j)
{
visited[i][j] = true;
cc[i][j] = c_idx;
cc_sz[c_idx]++;
for(int k = 0; k < 4; k++)
{
int ni = i+di[k], nj = j+dj[k];
if(ni < 0) ni += n;
if(ni >= n) ni -= n;
if(nj < 0) nj += m;
if(nj >= m) nj -= m;
if(!visited[ni][nj] && mmap[i][j] == mmap[ni][nj])
dfs(ni, nj);
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
scanf(" %c", &mmap[i][j]);
for(int i = 0; i < 7*n; i++)
for(int j = 0; j < 7*m; j++)
mmap2[i][j] = mmap[i%n][j%m];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(!visited[i][j])
{
c_idx++;
dfs(i, j);
}
for(int i = 0; i < 7*n; i++)
for(int j = 0; j < 7*m; j++)
if(!visited2[i][j])
{
c_idx2++;
dfs2(i, j);
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
bool check = false;
for(int ddi = 0; ddi < 7; ddi++)
for(int ddj = 0; ddj < 7; ddj++)
{
if(ddi == 3 && ddj == 3) continue;
if(cc2[i+n*3][j+m*3] == cc2[i+ddi*n][j+ddj*m])
check = true;
}
if(check) printf("-1 ");
else printf("%d ", cc_sz[cc[i][j]]);
}
printf("\n");
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |