글 읽기 - 1992번 쿼드 트리 문제 뭐가 잘못된건지 모르겠습니다.

youngjae6 5년 전 0

주어진 테스트 데이터에 대해선 맞게 작동하는데

자꾸 틀렸다고 뜨네요...

연습장에 펜으로 끄적이면서 회귀구문을 따라가봤는데

아무리 생각해도 제가 맞는 것 같은데

뭐가 잘못된건지 모르겠습니다...

#include <cstdio>
#include <cstdlib>

char **map;
char temp;
bool isSame;
bool temp_same;

void quadtree(int x, int y, int L);

int main(void) {
	int M;

	scanf("%d", &M);

	map = (char**)malloc(sizeof(char*)*M);
	for (int i = 0; i < M; i++) {
		map[i] = (char*)malloc(sizeof(char)*M);
	}
	//character를 scanf 할 때는 반드시 getchar() 해줘야함!
	getchar();
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%c", &map[i][j]);
		}
		getchar();
	}
	quadtree(0, 0, M);

	for (int i = 0; i < M; i++) {
		free(map[i]);
	}
	free(map);
}

void quadtree(int x, int y, int L) {
	printf("(");
	//1
	temp = map[y][x];
	isSame = true;
	for (int i = y; (i < y + L/2)&&isSame; i++) {
		for (int j = x; (j < x + L/2)&&isSame; j++) {
			if (temp != map[i][j]) {
				isSame = false;
				temp_same = isSame; //recursion 끝나고 복귀 했을 때 flag 상태 저장
				quadtree(x, y, L / 2);
				isSame = temp_same; //저장된 flag 상태 return!
			}
			else if ((i == y + L / 2 - 1) && (j == x + L / 2 - 1) && isSame)
				printf("%c", map[i][j]);
		}
	}
	//2
	temp = map[y][x + L / 2];
	isSame = true;
	for (int i = y; (i < y + L / 2)&&isSame; i++) {
		for (int j = x+L/2; (j < x + L)&&isSame; j++) {
			if (temp != map[i][j]) {
				isSame = false;
				temp_same = isSame;
				quadtree(x + L / 2, y, L / 2);
				isSame = temp_same;
			}
			else if ((i == y + L / 2 - 1) && (j == x + L - 1) && isSame)
				printf("%c", map[i][j]);
		}
	}
	//3
	temp = map[y + L / 2][x];
	isSame = true;
	for (int i = y+L/2; (i < y + L)&&isSame; i++) {
		for (int j = x; (j < x + L / 2)&&isSame; j++) {
			if (temp != map[i][j]) {
				isSame = false;
				temp_same = isSame;
				quadtree(x, y + L / 2, L / 2);
				isSame = temp_same;
			}
			else if ((i == y + L - 1) && (j == x + L / 2 - 1) && isSame)
				printf("%c", map[i][j]);
		}
	}
	//4
	temp = map[y + L / 2][x + L / 2];
	isSame = true;
	for (int i = y+L/2; (i < y + L)&&isSame; i++) {
		for (int j = x+L/2; (j < x + L)&&isSame; j++) {
			if (temp != map[i][j]) {
				isSame = false;
				temp_same = isSame;
				quadtree(x + L / 2, y + L / 2, L / 2);
				isSame = temp_same;
			}
			else if ((i == y + L - 1) && (j == x + L - 1) && isSame)
				printf("%c", map[i][j]);
		}
	}
	printf(")");
}

jh05013 5년 전 1

2
11
11

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1992번 쿼드 트리 문제 뭐가 잘못된건지 모르겠습니다.

youngjae6 5년 전 0

jh05013 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말