Submission #22823

#	Time	Username	Problem	Language	Result	Execution time	Memory
22823		현우야 이거 플로우야 (#40)	Young Zebra (KRIII5_YZ)	C++14	2 / 7	79 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(cost[cy][cx][di]==-INF) {					
					cost[cy][cx][di]=ncost;
					que.push(ip(cy,cx));
				}
				else {
					int dist=0;
					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<2;k++) {
					flag=Check(i,j,k);
					if(flag) break;
				}
				BFS(i,j,flag);
			}
		}
	}

	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++)
			printf("%d ",res[i][j]);
		puts("");
	}

	return 0;
}

Compilation message (stderr)

YZ.cpp: In function 'int main()':
YZ.cpp:100: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:102: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