글 읽기 - 17142 반례좀 찾아주세요 (c++)

snrk2010 4년 전 0

78%에서 항상틀립니다. ㅠㅠ

#include <algorithm>
#include <vector>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int N, M;
struct info {
	int row, col, cnt;
};
int map[50][50];
char dnt[50][50];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
vector<pair<int, int> > start_num;
int solve(vector<int> idx) {
	memset(dnt, '0', sizeof(dnt));
	int num = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 2) dnt[i][j] = '*';
			else if (map[i][j] == 1) dnt[i][j] = '-';
			else if (map[i][j] == 0) num += 1;
		}
	}
	queue<info> q;
	int result = 0;
	for (int i = 0; i < M; i++) q.push({ start_num[idx[i]].first,start_num[idx[i]].second,0 });
	while (!q.empty()) {
		info tmp = q.front(); q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int tx = tmp.row + dx[dir], ty = tmp.col + dy[dir];
			if (tx < 0 || ty < 0 || tx >= N || ty >= N) continue;
			if (dnt[tx][ty] == '-') continue;
			if (dnt[tx][ty] == '0' || dnt[tx][ty] == '*') {
				if (dnt[tx][ty] == '0') num -= 1;
				dnt[tx][ty] = tmp.cnt + '0' + 1;
				q.push({ tx,ty,tmp.cnt + 1 });
				result = max(result, tmp.cnt + 1);
				if (num <= 0) return result;
			}
		} 
	}
	return 987654321;
}
int ans;
void dfs(int index, vector<int> idx) {
	if (idx.size() == M) {
		ans = min(ans, solve(idx));
		return;
	}
	if (index >= start_num.size()) return;
	idx.push_back(index);
	dfs(index + 1, idx);
	idx.pop_back();
	dfs(index + 1, idx);
}
void init() {
	cin >> N >> M;
	start_num.clear();
	ans = 987654321;
	memset(map, 0, sizeof(map));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) start_num.push_back(make_pair(i, j));
		}
	}
}
int main() {
	init();
	vector<int> idx;
	bool flag = false;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0) flag = true;
		}
	}
	if (!flag) { cout << 0 << endl;}
	else {
		dfs(0, idx);
		if (ans == 987654321) cout << -1 << endl;
		else cout << ans << endl;
	}
}

rhdqor213 4년 전 2

dnt를 char형으로 하면 36번째 줄에서 char형의 범위를 초과하여 문제를 일으킬 수 있습니다. int형으로 푸시는 것을 추천드립니다.

snrk2010 4년 전 1

좋은지적 감사합니다. 생각지도 못했네요^^ 덕분에 풀었습니다.

simoolook 3년 전 0

저도 char 때문에 틀렸었네요 ㅜㅜㅜ 감사합니다 정말....

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

문제

문제

출처

ICPC

17142 반례좀 찾아주세요 (c++)

snrk2010 4년 전 0

rhdqor213 4년 전 2

snrk2010 4년 전 1

simoolook 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말