글 읽기 - 반례나 고칠 부분을 찾고싶습니다.

jhlim 5년 전 0

dfs 재귀함수를 사용했습니다. main의 배열 scanf 후 처리가 좀 더러운데 그냥 받은 점좌표를 배열에서 직접 칠해보려고 한거라... 직접 print해서 배열이 예쁘게 그려지는건 확인해봤습니다.

질문글들 뒤져보면서 찾은 예제들은 전부 잘 수행이 되는데 에러가 어디서 난걸까요?ㅠㅠ

# include <stdio.h>
# include <stdlib.h>
# define _CRT_SECURE_NO_WARNINGS

int M, N, K;
int A[100][100] = { 0, };
int visited[100][100] = { 0, };
int cnt = 0;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int num = 0;
int ans[10000];

void DFS(int a, int b) {
	int x, y;
    num++;
	visited[a][b] = 1;
	for (int k = 0; k < 4; k++) {
		x = a + dx[k];
		y = b + dy[k];
		if (x < M && y < N) {
			if (A[x][y] == 1 && visited[x][y]==0) {
				DFS(x, y);
			}
		}
	}
}

int main() {
	int x1, x2, y1, y2;
	int min = 100;
	int check = 0;
	int temp = 0;

	scanf("%d %d %d", &M, &N, &K);

	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			visited[i][j] = 1;
		}
	}

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			A[i][j] = 1;
			visited[i][j] = 0;
		}
	}

	for (int k = 0; k < K; k++) {
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		// (x1,y1) = (M-y1)(x1)

		for (int i = (M - y2); i < (M - y1); i++) {
			for (int j = x1; j < x2; j++) {
				A[i][j] = 0;
			}

		}
	}

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (A[i][j] == 1 && !visited[i][j]) {
				DFS(i, j);
				ans[cnt] = num;
				cnt++;
				num = 0;
			}
		}
	}

	printf("%d\n", cnt);

	while (1) {
		for (int i = 0; i < cnt; i++) {
			if (temp < ans[i] && ans[i] < min) {
				min = ans[i];
			}
		}
		printf("%d", min);
		temp = min;
		min = 100;
		check++;
		if (check >= cnt) {
			break;
		}
        printf(" ");
	}

	return 0;
}

djm03178 5년 전 1

우선, 19, 20번째 줄에서 x와 y는 음수가 될 수 있으니, 21번째 줄에서 음수로도 가지 못하게 막아줘야 합니다.

그걸 고치면, 다음과 같은 입력에서 틀립니다.

100 100 1

0 0 1 1

jhlim 5년 전 0

감사합니다!

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

문제

문제

출처

ICPC

반례나 고칠 부분을 찾고싶습니다.

jhlim 5년 전 0

djm03178 5년 전 1

jhlim 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말