제출 #22569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22569		현우야 이거 플로우야 (#40)	Young Zebra (KRIII5_YZ)	C++11	2 / 7	113 ms	8036 KiB

YZ

#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) 메시지

YZ.cpp: In function 'int main()':
YZ.cpp:112:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
YZ.cpp:114:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",str[i]);
                     ^

• Subtask 1: 2 / 7