글 읽기 - 반례를 도저히 못찾겠습니다.

stbnswk98 3년 전 0

테스트 케이스 전부 통과하고 질문에 등록된 테스트 케이스도 전부 통과하는데,

58%에서 틀렸다고 나옵니다.

어느 부분에서 틀린건지, 코드가 비록 난해하지만, 반례 찾아주시면 정말 감사하겠습니다 ㅠㅠ

#include <iostream>
#include <vector>

struct Virus {
	int x;
	int y;
};
struct Map {
	int map[50][50];
}map;

using namespace std;
vector <Virus> candi;
vector <Virus> pick;
vector <Virus> temp;
vector <Virus> temp_pick;
int N, M;
int res = 10000;
int t;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int zero_count;

int spread() {
	int count = 0;

	//활성형 바이러스는 3으로 표시.

	for (int i = 0; i < M; i++) {
		map.map[pick[i].y][pick[i].x] = 3;
	}

	while (t <= 2500) {

		//spreading
		if (pick.empty()) return 10001;
		t++;
		while (1) {
			int x = pick.back().x;
			int y = pick.back().y;
			map.map[y][x] = 3;
			for (int n = 0; n < 4; n++) {
				int nx = x + dx[n];
				int ny = y + dy[n];
				if (0 <= nx && nx < N && 0 <= ny && ny < N) {
					if (map.map[ny][nx] == 0) {
						map.map[ny][nx] = 3;
						if (++count == zero_count) return t;
						Virus virus_temp;
						virus_temp.y = ny; virus_temp.x = nx;
						temp.push_back(virus_temp);
					}
					else if (map.map[ny][nx] == 2) {
						map.map[ny][nx] = 3;
						Virus virus_temp;
						virus_temp.y = ny; virus_temp.x = nx;
						temp.push_back(virus_temp);
					}
				}
			}
			pick.pop_back();
			if (pick.empty()) {
				while (!temp.empty()) {
					pick.push_back(temp.back());
					temp.pop_back();
				}
				break;
			}
		}
	}
	return 10001;
}

void dfs(int index) {
	if (pick.size() == M) {
		temp_pick.clear();
		for (int j = pick.size()-1; j >=0; j--) {
			temp_pick.push_back(pick[j]);
		}
		t = 0;
		int temp_res = spread();
		if (temp_res < res) res = temp_res;
		pick.clear();
		for (int j = temp_pick.size() - 1; j >= 0; j--) {
			pick.push_back(temp_pick[j]);
		}
		return;
	}
	for (int i = index; i < candi.size(); i++) {
		//backup
		//update
		Map temp_map = map;
		pick.push_back(candi[i]);
		dfs(i + 1);
		//restore
		map = temp_map;
		pick.pop_back();
		//여기서 쓸데없이 dfs(i+1) 또 했다.
	}
}

int main() {
	cin >> N >> M;
	//map reading & virus candi.
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map.map[y][x];
			if (map.map[y][x] == 2) {
				Virus virus_temp;
				virus_temp.x = x; virus_temp.y = y;
				candi.push_back(virus_temp);
			}
			if (map.map[y][x] == 0) zero_count++;
		}
	}
	if (zero_count == 0) {
		cout << "0" << endl; return 0;
	}
	
	dfs(0);
	if (res == 10000) cout << "-1" << endl;
	else cout << res << endl;
}

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

문제

문제

출처

ICPC

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

stbnswk98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말