글 읽기 - 14%에서 틀립니다.

lonecitizen 4년 전 0

도저히 반례를 못찾겠습니다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int map[51][51], N, M, _count = 0, ans = 2e9, dir[4][2] = { {1,0}, {0, 1}, {0, -1}, {-1, 0} };
vector<pair<int, int> > virus;
vector<int> combi;

void BFS(vector<int> v) {
	int temp[51][51], _max = 0, localCnt = 0;
	for (int row = 1; row <= N; row++) {
		for (int col = 1; col <= N; col++) {
			if (map[row][col] == 2 || map[row][col] == 0) temp[row][col] = 0;
			else temp[row][col] = -1;
		}
	}

	queue<pair<int, int>> q;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == 1) {
			q.push(virus[i]);
		}
	}

	while (!q.empty()) {
		int row = q.front().first;
		int col = q.front().second;

		q.pop();

		for (int d = 0; d < 4; d++) {
			int nrow = row + dir[d][0];
			int ncol = col + dir[d][1];

			if (nrow < 1 || ncol < 1 || nrow > N || ncol > N) continue;
			if (temp[nrow][ncol] == -1) continue;
			if (temp[nrow][ncol] > 0) continue;

			q.push(make_pair(nrow, ncol));
			temp[nrow][ncol] = temp[row][col] + 1;
			if (map[nrow][ncol] != 2) localCnt++;
		}
	}

	for (int row = 1; row <= N; row++) {
		for (int col = 1; col <= N; col++) {
			if (temp[row][col] > _max) {
				if (map[row][col] != 2) 
					_max = temp[row][col];
			}
		}
	}

	if (_max < ans && localCnt == _count) ans = _max;
}
int main()
{
	cin >> N >> M;
	for (int row = 1; row <= N; row++) {
		for (int col = 1; col <= N; col++) {
			cin >> map[row][col];
			if (map[row][col] == 2) virus.push_back(make_pair(row, col));
			else if (map[row][col] == 0) _count++;
		}
	}


	for (int idx = 0; idx < virus.size() - M; idx++) combi.push_back(0);
	for (int idx = virus.size() - M; idx < virus.size(); idx++)	combi.push_back(1);

	BFS(combi);
	while (next_permutation(combi.begin(), combi.end())) {
		BFS(combi);
	}

	if (ans == 2e9) ans = -1;
	cout << ans;
}

lonecitizen 4년 전 0

반례 찾았습니다

5 3

2 2 2 0 0

1 1 1 1 1

정답은 2 입니다.

visit 따로 확인 안하고 임시로 생성한 2차원 배열에서 0보다 크면 방문한 것으로 간주하도록 짰었는데

이렇게 구현했더니 꼬이는 부분이 있었습니다.

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

문제

문제

출처

ICPC

14%에서 틀립니다.

lonecitizen 4년 전 0

lonecitizen 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말