# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22431 | STARBUCKS (#40) | Young Zebra (KRIII5_YZ) | C++98 | 0 ms | 2144 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 <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <utility>
#include <string>
#include <set>
#include <map>
using namespace std;
char A[120][120];
int d[120][120];
int visit[120][120];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n, m;
const int INF = 1207;
int dfs(int x, int y, char c)
{
if(x == 0 || x == 3*n-1 || y == 0 || y == 3*m-1) return INF;
if(visit[x][y]) return 0;
if(d[x][y] != -2) return d[x][y];
visit[x][y] = 1;
int ret = 0;
for(int i=0; i<4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(A[nx][ny] == c) ret += dfs(nx, ny, c);
}
// cout << x << ' ' << y << ' ' << ret + 1 << ' ' << endl;
return d[x][y] = ret + 1;
}
void fill(int x, int y, char c, int ans)
{
if(x == 0 || x == 3*n-1 || y == 0 || y == 3*m-1) return;
if(visit[x][y] == 2) return;
visit[x][y] = 2;
d[x][y] = ans;
for(int i=0; i<4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(A[nx][ny] == c) fill(nx, ny, c, ans);
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
scanf(" %c ", &A[i][j]);
for(int ii=0; ii<3; ii++)
{
for(int jj=0; jj<3; jj++)
{
A[n*ii+i][m*jj+j] = A[i][j];
d[n*ii+i][m*jj+j] = -2;
}
}
}
}
// for(int i=0; i<3*n; i++)
// {
// for(int j=0; j<3*m; j++)
// {
// printf("%c", A[i][j]);
// } printf("\n");
// }
for(int i=n; i<2*n; i++)
{
for(int j=m; j<2*m; j++)
{
int t = dfs(i, j, A[i][j]);
for(int ii=0; ii<3; ii++)
{
for(int jj=0; jj<3; jj++)
{
fill((ii-1)*n+i, (jj-1)*m+j, A[i][j], t);
}
}
printf("%d ", d[i][j] >= INF ? -1 : d[i][j]);
// printf("%d ", t);
} printf("\n");
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |