답안 #22877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22877	2017-04-30T07:58:07 Z	도치피치피보족(#942, lyzqm123)	Young Zebra (KRIII5_YZ)	C++14	0 / 7	69 ms	10268 KB

YZ

#include <cstdio>
#include <queue>
using namespace std;
int dy[] = { -1, 0, 0, 1 }, dx[] = { 0, 1, -1, 0 };
char input[401][401];
char map[1204][1204];
int group[20000];
int N, M, G = 1;
int visit[401][401];
int vvisit[1204][1204] = { 0 };
queue<pair<int, int>> qq;
void bfs(int iy, int ix){
	char ch = input[iy][ix];
	queue<pair<int, int>> q;

	q.push({ iy, ix });
	qq.push({ iy + N, ix + M });
	visit[iy][ix] = G;
	vvisit[iy + N][ix + M] = G;
	while (!q.empty()){
		int y = q.front().first, x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++){
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M || visit[ny][nx] > 0) continue;
			if (input[ny][nx] == ch){
				visit[ny][nx] = G;
				vvisit[ny + N][nx + M] = G;
				q.push({ ny, nx });
				qq.push({ ny + N, nx + M});
			}
		}
	}
}
int bfs2(char ch){
	int cnt = 0;
	bool flag = false;
	while (!qq.empty()){
		int y = qq.front().first, x = qq.front().second;
		qq.pop();

		cnt++;

		for (int i = 0; i < 4; i++){
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 0 || ny >= 3 * N || nx < 0 || nx >= 3 * M){ flag = true; continue; }
			if (map[ny][nx] == ch && vvisit[ny][nx] != G){	
				qq.push({ ny, nx });
				vvisit[ny][nx] = G;
			}
		}
	}
	if (flag) return -1;
	else return cnt;
}
int main(){
	scanf("%d%d", &N, &M);
	for (int n = 0; n < N; n++)
		scanf("%s", input[n]);

	for (int n = 0; n < 3 * N; n++){
		for (int m = 0; m < 3 * M; m++){
			map[n][m] = input[n%N][m%M];
		}
	}

	for (int n = 0; n < N; n++){
		for (int m = 0; m < M; m++){
			if (visit[n][m] == 0){
				bfs(n,m);
				int ans = bfs2(input[n][m]);
				group[G] = ans;
				G++;
			}
		}
	}

	for (int n = 0; n < N; n++){
		for (int m = 0; m < M; m++)
			printf("%d ", group[visit[n][m]]);
		printf("\n");
	}

	return 0;
}

Compilation message

YZ.cpp: In function 'int main()':
YZ.cpp:57:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
YZ.cpp:59:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", input[n]);
                        ^

Subtask #1

0.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	10268 KB	Output is correct
2	Incorrect	49 ms	10008 KB	Output isn't correct
3	Halted	0 ms	0 KB	-