# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
22758 | 퍼플달고싶다 (#40) | Young Zebra (KRIII5_YZ) | C++98 | 486 ms | 39328 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define SIZE 31600000
#define BC 50
#define BS 5000
#define MOD 1000000007LL
#define MAXV 555
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef vector<vector<long long> > mat;
int n,m;
char str[444][444];
bool bd[1222][1222];
bool visited[1222][1222];
int sz[1222][1222];
pair<int, int> p[1222][1222];
int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};
pair<int, int> find(pair<int, int> u) {
if(p[u.fi][u.se] == u) return u;
return p[u.fi][u.se] = find(p[u.fi][u.se]);
}
void merge(pair<int, int> u, pair<int, int> v) {
u = find(u), v = find(v);
if(u == v) return;
p[u.fi][u.se] = v;
sz[v.fi][v.se] += sz[u.fi][u.se];
}
bool ok(int y, int x) {return y>=0 && y<3*n && x>=0 && x<3*m;}
void bfs(int y, int x) {
queue<pair<int, int > > q;
q.push({y,x});
visited[y][x] = 1;
while(!q.empty()) {
int hy = q.front().fi, hx = q.front().se;
// printf("here %d %d\n",hy,hx);
q.pop();
for(int i=0;i<4;i++) {
int ny = hy + dy[i], nx = hx + dx[i];
if(ny < 0) ny += 3*n;
if(nx < 0) nx += 3*m;
if(ny >= 3*n) ny -= 3*n;
if(nx >= 3*m) nx -= 3*m;
if(ok(ny,nx) && visited[ny][nx] == 0 && (bd[y][x] == bd[ny][nx])) {
merge({y,x}, {ny,nx}), q.push({ny,nx}), visited[ny][nx] = 1;
}
}
}
}
int main () {
for(int i=0;i<1222;i++) for(int j=0;j<1222;j++) p[i][j] = {i,j}, sz[i][j] = 1;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",str[i]);
for(int yc=0;yc<3;yc++)
for(int xc=0;xc<3;xc++)
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
bd[yc*n+i][xc*m+j] = str[i][j] == 'B' ? 1 : 0;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
int y = n+i, x = m+j;
if(visited[y][x] == 0) bfs(y,x);
pair<int, int> root = find({y,x});
printf("%d ",sz[root.fi][root.se]);
}
printf("\n");
}
// for(int i=0;i<100;i++) {
// for(int j=0;j<100;j++) printf("%d ",sz[i][j]);
// printf("\n");
// }
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |