글 읽기 - 다른 질문에 올려주신 예제까지도 돌아가는데..

smucs13 4년 전 0

예제는 잘 돌아갑니다!

다른 질문에서 다른분들께서 올려주신 예제까지도 잘 돌아가는데

틀려습니다가 뜨네요ㅠ 무슨 이유인지 잘 모르겠습니다

// https://www.acmicpc.net/problem/14502

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAX = 9;
int N, M, ans = 3;
int MAP[MAX][MAX];
int CMAP[MAX][MAX];
bool check[MAX][MAX];

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

vector<pair<int, int>> virus;

void show() {
	cout << "--------------------------------------------" << '\n';
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << MAP[i][j] << ' ';
		}
		cout << '\n';
	}
}

void copy_map() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			CMAP[i][j] = MAP[i][j];
		}
	}
}

bool is_Range(int nx, int ny) {
	if (nx >= 0 && nx < N && ny >= 0 && ny < M)
		return true;
	else
		return false;
}

int count_safety() {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (CMAP[i][j] == 0) {
				cnt++;
			}
		}
	}
	return cnt;
}

void bfs() {
	queue<pair<int, int>> q;
	int size = virus.size();
	for (int i = 0; i < size; i++) {
		q.push(make_pair(virus[i].first, virus[i].second));
	}

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (is_Range(nx, ny)) {
				if (CMAP[nx][ny] == 0 && check[nx][ny] == false) {
					CMAP[nx][ny] = 2;
					q.push(make_pair(nx, ny));
					check[nx][ny] = true;
				}
			}
		}
	}


}

void dfs(int cnt) {
	if (cnt == 3) {
		copy_map();
		bfs();
		//show();
		int res = count_safety();
		ans = max(ans, res);

		memset(check, false, sizeof(check));
		return;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (MAP[i][j] == 0) {
				MAP[i][j] = 1;
				dfs(cnt + 1);
				MAP[i][j] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> MAP[i][j];
			if (MAP[i][j] == 2) {
				virus.push_back(make_pair(i, j));
				check[i][j] = true;
			}
		}
	}

	dfs(0);

	cout << ans << '\n';

	return 0;
}

nahwasa 4년 전 1

반례입니다.

smucs13 4년 전 1

nahwasa

헉 감사합니다.. 빈공간이 무조건 3개 이상이라는 말로 인해

ans를 3으로 초기화 시켜놨네요ㅠ

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

문제

문제

출처

ICPC

다른 질문에 올려주신 예제까지도 돌아가는데..

smucs13 4년 전 0

nahwasa 4년 전 1

smucs13 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말