글 읽기 - 예제는 다 맞지만 1%도 안올라갑니다..

tjrwo3080 4년 전 0

일단 제 코드의 순서입니다.

1. 입력과 동시에 각 섬의 번호를 계산하여 저장한다.

2. 이후 각 섬의 테두리 부분을 벡터(island)에 저장한다

3. 각 벡터의 요소들끼리 거리 계산을 하여 정답을 산출한다.

일단 비쥬얼 환경에서는 나와있는 모든 예제가 다 통과됩니다 ㅠㅠ

도대체 어디가 문제일까요....

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

struct Pos {
	int x, y;
};

vector<vector<Pos>> island;
int arr[102][102] = { 0, };
int N, num, dis, answer;

void merge(int i, int j, int n) {
	arr[i][j] = n;
	if (1 < i && 0 < arr[i - 1][j] && arr[i - 1][j] != n)
		merge(i - 1, j, n);
	if (1 < j && 0 < arr[i][j - 1] && arr[i][j - 1] != n)
		merge(i, j - 1, n);
	return;
}

void solve() {
	island.resize(num + 1);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (arr[i][j] && (!arr[i][j + 1] || !arr[i][j - 1] || !arr[i + 1][j] || !arr[i - 1][j])) {
				island[arr[i][j]].push_back({ i, j });
			}
		}
	}

	for (int i = 1; i < num; i++) {
		for (int j = i + 1; j <= num; j++) {
			int island_i_size = island[i].size();
			int island_j_size = island[j].size();
			for (int a = 0; a < island_i_size; a++) {
				for (int b = 0; b < island_j_size; b++) {
					dis = abs(island[i][a].x - island[j][b].x) + abs(island[i][a].y - island[j][b].y) - 1;
					if (dis < answer) {
						answer = dis;
					}
				}
			}
		}
	}
}

void init() {
	cin >> N;
	num = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
			if (arr[i][j]) {
				if (arr[i - 1][j] && arr[i][j - 1] && arr[i - 1][j] != arr[i][j - 1]) {
					merge(i - 1, j, arr[i][j - 1]);
					arr[i][j] = arr[i][j - 1];
				}
				else if (arr[i - 1][j]) {
					arr[i][j] = arr[i - 1][j];
				}
				else if (arr[i][j - 1]){
					arr[i][j] = arr[i][j - 1];
				}
				else {
					arr[i][j] = ++num;
				}
			}
		}
	}

	answer = 2000;
	solve();
	cout << answer << endl;
}

int main(void) {
	init();
	return 0;
}

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

문제

문제

출처

ICPC

예제는 다 맞지만 1%도 안올라갑니다..

tjrwo3080 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말