# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
22569 | 현우야 이거 플로우야 (#40) | Young Zebra (KRIII5_YZ) | C++11 | 113 ms | 8036 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>
const int INF=987654321;
typedef std::pair<int, int> ip;
const int dy[4]={0,1,0,-1}, dx[4]={1,0,-1,0};
int n,m,cost[500][500][4],vis[500][500],res[500][500];
char str[500][500];
int abs(int a) {
return a<0 ?-a:a;
}
int gety(int y, int d) {
y+=dy[d];
if(y<0) y+=n;
else if(y>=n) y-=n;
return y;
}
int getx(int x, int d) {
x+=dx[d];
if(x<0) x+=m;
else if(x>=m) x-=m;
return x;
}
bool Check(int sy, int sx, int di) {
int len;
if(di==0||di==2) len=m;
else len=n;
std::queue<ip> que;
que.push(ip(sy,sx));
cost[sy][sx][di]=0;
while(!que.empty()) {
ip now=que.front();que.pop();
for(int k=0;k<4;k++) {
int ncost=cost[now.first][now.second][di];
if(k==di) ncost++;
else if((k+2)%4==di) ncost--;
int cy=gety(now.first,k), cx=getx(now.second,k);
if(str[cy][cx]==str[sy][sx]) {
/*if(cy==6&&cx==10&&di==0){
printf("%d %d\n",cost[cy][cx][di],now.first);
printf("!!!");
}*/
// printf("%d %d %d %d\n",cy,cx,di,ncost);
// printf("%d\n",cost[cy][cx][di]);
if(cost[cy][cx][di]==-INF) {
cost[cy][cx][di]=ncost;
que.push(ip(cy,cx));
// if(cy==0 && cx==1) puts("##");
}
else {
// printf("%d %d %d %d %d %d\n",cy,cx,now.first,now.second,cost[now.first][now.second][di],cost[cy][cx][di]);
int dist=0;
/*if(cy==6&&cx==10&&di==0) {
printf("@@@");
printf("%d %d %d\n",cost[cy][cx][di], cost[now.first][now.second][di], dist);
}*/
if(di==k || (k+2)%4==di) dist=1;
if(abs(cost[now.first][now.second][di]-cost[cy][cx][di])+dist==len) {
return true;
}
}
}
}
}
return false;
}
void BFS(int sy, int sx, bool chk) {
std::queue<ip> que;
que.push(ip(sy,sx));
if(chk) res[sy][sx]=-1;
vis[sy][sx]=1;
int sz=1;
while(!que.empty()) {
ip now=que.front();que.pop();
for(int k=0;k<4;k++) {
int cy=gety(now.first,k), cx=getx(now.second,k);
if(vis[cy][cx]==0&&str[cy][cx]==str[sy][sx]) {
que.push(ip(cy,cx));
vis[cy][cx]=1;
if(chk) res[cy][cx]=-1;
++sz;
}
}
}
if(chk) return;
que.push(ip(sy,sx));
res[sy][sx]=sz;
vis[sy][sx]=2;
while(!que.empty()) {
ip now=que.front();que.pop();
for(int k=0;k<4;k++) {
int cy=gety(now.first,k), cx=getx(now.second,k);
if(str[cy][cx]==str[sy][sx]&&vis[cy][cx]==1) {
que.push(ip(cy,cx));
vis[cy][cx]=2;
res[cy][cx]=sz;
}
}
}
}
int main() {
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",str[i]);
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int k=0;k<4;k++)
cost[i][j][k]=-INF;
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(vis[i][j]==0) {
bool flag=false;
for(int k=0;k<4;k++) {
flag=Check(i,j,k);
if(flag) break;
}
BFS(i,j,flag);
}
}
}
// printf("!! %d %d\n",cost[0][1][0], cost[0][2][0]);
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++)
printf("%d ",res[i][j]);
puts("");
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |