글 읽기 - [영역 구하기] 반례나 잘못된 부분을 알고 싶습니다.

hong4243 6년 전 0

채점이 정상적으로 되다가 한 10%쯤에서 틀렸다고 나오는데 이유를 못찾겠습니다...

혹시 반례나 이유아시는분 알려주시면 정말 감사할것 같습니다!!

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

int n, m, k;
int map[101][101] = { 0 };
int leftX, leftY, rightX, rightY;

int result = 0;
int cnt[1001] = { 0 };

int dirX[4] = { 0,0,1,-1 };
int dirY[4] = { 1,-1,0,0 };

void input();
void mark(int leftX, int leftY, int rightX, int rightY);


int compare(const void* a, const void* b) {

	if (*(int *)a > *(int*)b) return 1;
	else if (*(int*)a < *(int *)b) return -1;
	else return 0;
}//quick sort


void dfs(int col, int row, int count) {
	
	if (count > cnt[result - 1]) {
		cnt[result - 1] = count;
	}

	map[col][row] = result;//Mark the map.

	for (int i = 0; i < 4; i++) {
		int tmpCol, tmpRow;
		tmpCol = col + dirY[i];
		tmpRow = row + dirX[i];

		if (tmpCol >= 0 && tmpCol < m && tmpRow >=0 && tmpRow < n && map[tmpCol][tmpRow] == 0) {
			dfs(tmpCol, tmpRow, count + 1);
		}
	}
}


int main()
{
	input();

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				result++;
				map[i][j] = result;
				dfs(i, j, 0);
			}
		}
	}

	qsort(cnt, result* sizeof(int) / sizeof(int), sizeof(int), compare);//sort

	//////// PRINT ////////////////////////
	printf("%d\n", result);
	for (int i = 0; i < 3; i++) {
		printf("%d ", cnt[i]+1);
	}
	////////////////////////////////////////
}

void input(){// Functions that receive input first

	scanf("%d %d %d", &m, &n, &k);

	for (int i = 0; i < k; i++) {
		scanf("%d %d %d %d", &leftX, &leftY, &rightX, &rightY);
		mark(leftX, leftY, rightX, rightY);// Mark the map.
	}
}

void mark(int leftX, int leftY, int rightX, int rightY) {

	for (int i = leftY; i < rightY; i++) {
		for (int j = leftX; j < rightX; j++) {
			map[m-i-1][j] = 9;
		}
	}
}

/*
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

*/

atomzeno 6년 전 1

65줄에서 왜 i<3인가용? 영역 개수는 테스트케이스마다 다를 수 있지 않나용?

atomzeno 6년 전 1

그리고 if (count > cnt[result - 1]) { cnt[result - 1] = count; }는 왜 있는 건가용?

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

문제

문제

출처

ICPC

[영역 구하기] 반례나 잘못된 부분을 알고 싶습니다.

hong4243 6년 전 0

atomzeno 6년 전 1

atomzeno 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말