Submission #22878

#	Time	Username	Problem	Language	Result	Execution time	Memory
22878		크리님 제가 귀여우면 됬지 뭘 더 원하세요 진짜 (#40)	Young Zebra (KRIII5_YZ)	C++14	0 / 7	29 ms	4984 KiB

YZ

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<list>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<functional>
#include<cmath>
#include<string>

#define sd(a) scanf("%d", &a)
#define sld(a) scanf("%lld", &a)

using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;

int xx[4] = { 0, 0, -1, 1 };
int yy[4] = { -1, 1, 0, 0 };

int N, M;
int locc = 1;
char mama[410][410];
int loc[410][410];
int check[410][410];
int ans[410][410];

int num[410];
int len[410];
int dat[410];
int find(int a) {
	if (num[a] != a) {
		a = num[a];
	}
	return a;
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);

	if (len[a] < len[b]) {
		num[a] = b;
	}
	else {
		num[b] = a;
	}
}

void init_check() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			check[i][j] = 0;
		}
	}
}
int dfs(int x, int y) {
	if (check[x][y] == 1) {
		return 0;
	}
	check[x][y] = 1;

	int ret = 1;

	for (int i = 0; i < 4; i++) {
		int next_x = x + xx[i];
		int next_y = y + yy[i];

		if (0 < next_x && next_x <= N && 0 < next_y && next_y <= M) {
			if (mama[next_x][next_y] == mama[x][y]) {
				ret += dfs(x + xx[i], y + yy[i]);
			}
		}
	}

	return ret;
}
void dfs2(int x, int y, int value, int lo) {
	if (check[x][y] == 2) {
		return;
	}
	check[x][y] = 2;
	ans[x][y] = value;
	loc[x][y] = lo;

	for (int i = 0; i < 4; i++) {
		int next_x = x + xx[i];
		int next_y = y + yy[i];

		if (0 < next_x && next_x <= N && 0 < next_y && next_y <= M) {
			if (mama[next_x][next_y] == mama[x][y]) {
				dfs2(x + xx[i], y + yy[i], value, lo);
			}
		}
	}
}

int main(void) {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		getchar();
		for (int j = 1; j <= M; j++) {
			mama[i][j] = getchar();
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (check[i][j] == 0) {
				dat[locc] = dfs(i, j);
				dfs2(i, j, dat[locc], locc);
				num[locc] = locc;
				locc++;
			}
		}
	}

	init_check();
	for (int i = 1; i <= N; i++) {
		if (mama[i][1] == mama[i][M]) {
			if (find(loc[i][1]) == find(loc[i][M])) {
				int aa = find(loc[i][1]);
				int bb = find(loc[i][M]);
				merge(aa, bb);
				aa = find(aa);
				dfs2(i, 1, -1, aa);
				dat[aa] = -1;
			}
			else {
				int aa = find(loc[i][1]);
				int bb = find(loc[i][M]);
				int temp = dat[aa] + dat[bb];
				merge(aa, bb);
				aa = find(aa);
				dfs2(i, 1, temp, aa);
				dfs2(i, M, temp, aa);
				dat[aa] = temp;
			}
		}
	}
	init_check();
	for (int j = 1; j <= M; j++) {
		if (mama[1][j] == mama[N][j]) {
			if (find(loc[1][j]) == find(loc[N][j])) {
				int aa = find(loc[1][j]);
				int bb = find(loc[N][j]);
				merge(aa, bb);
				aa = find(aa);
				dfs2(1, j, -1, aa);
				dat[aa] = -1;
			}
			else {
				int aa = find(loc[1][j]);
				int bb = find(loc[N][j]);
				int temp = dat[aa] + dat[bb];
				merge(aa, bb);
				aa = find(aa);
				dfs2(1, j, temp, aa);
				dfs2(N, j, temp, aa);
				dat[aa] = temp;
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			ans[i][j] = dat[find(loc[i][j])];
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			printf("%d ", ans[i][j]);
		}
		printf("\n");
	}

	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 7