제출 #22501

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

YZ

#include <stdio.h>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>

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 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++) {
			if((k+2)%4==di) continue;

			int cy=gety(now.first,k), cx=getx(now.second,k);
			if(str[cy][cx]==str[sy][sx]) {
				// printf("%d %d %d %d\n",now.first,now.second,cy,cx);
				if(cost[cy][cx][di]==-1) {					
					cost[cy][cx][di]=cost[now.first][now.second][di]+(di==k);
					que.push(ip(cy,cx));
				}
				else if(di==k) {
					if(cost[now.first][now.second][di]-cost[cy][cx][di]+1==len) {
						// printf("%d %d %d %d\n",now.first,now.second,cy,cx);
						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]);

	memset(cost, -1, sizeof(cost));
	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);
				// puts("");
			}
		}
	}

	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:95: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:97: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