글 읽기 - 어느 부분에서 틀렸는지 알 수 있을까요??

ldg1291 3년 전 0

TC는 전부 성공하는데

시작하자 마자 틀렸습니다가 나오네요..

감사합니다

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

using namespace std;

vector<pair<int, int>> spot;
set<pair<int, int>> selected;
pair<int, int> mov[] = { {-1,0},{0,-1}, {1,0}, {0,1} };
int N, M;

int map[9][9];

int ans = 0;
int wall;

vector<pair<int, int>> v;

void bfs(vector<pair<int,int>> virus) {
	
	int count = virus.size();
	
	int visited[9][9] = { 0 };

	queue<pair<int, int>> que;

	for (int i = 0; i < virus.size(); i++) {
		que.push({ virus[i].first, virus[i].second });
		visited[virus[i].first][virus[i].second] = 1;
	}

	while (!que.empty()) {
		pair<int, int> f = que.front();
		que.pop();

		int nowx = f.first;
		int nowy = f.second;

		for (int i = 0; i < 4; i++) {
			int newx = f.first + mov[i].first;
			int newy = f.second + mov[i].second;
			if (newx >= 0 && newx < N && newy >= 0 && newy < M && map[newx][newy] == 0 && visited[newx][newy] == 0) {
				count++;
				visited[newx][newy] = 1;
				que.push({ newx, newy });
			}
		}
	}
	ans = max(ans, N*M - count - wall - 3);
}

void dfs(int start) {

	if (start >= spot.size() && selected.size() < 3) {
		return;
	} 
	if (selected.size() == 3) {
		bfs(v);
		return;
	}
	
	for (int i = start; i < spot.size(); i++) {
		selected.insert(spot[i]);
		map[spot[i].first][spot[i].second] = 1;
		dfs(i+1 + 1);
		selected.erase(spot[i]);
		map[spot[i].first][spot[i].second] = 0;
	}

}

int main()
{
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int n;
			scanf("%d", &n);
			if (n == 1) wall++;
			if (n == 2)v.push_back({ i,j });
			if (n == 0)spot.push_back({ i,j });
			map[i][j] = n;
		}
	}

	dfs(0);

	cout << ans << endl;
}

ldg1291 3년 전 0

WRONG 에 쓰신게 혹시 제 코드에서 나오는 결과인가요?

지금 제 컴퓨터에서 코드를 돌려보면 3번째 예시 빼고는 전부 Correct와 같은 답이 나오고있습니다.

3번째 예시도 제 컴퓨터에선 6이 나오는데 정답도 6이 맞는 것 같은데요..

jh05013 3년 전 0

세 번째의 경우 다음과 같이 막아서 7을 만들 수 있습니다.

jh05013 3년 전 0

나머지는 제가 컴파일 설정을 잘못한 것이 원인인 것 같습니다. 다시 반례를 만들어 왔습니다.

4
0 0 1
0 1 0
1 1 0
2 0 1
Correct: 7
WRONG: 6

5
0 0 1 0
1 1 1 0
0 0 2 0
1 0 0 0
Correct: 11
WRONG: 9

4
1 1 0
1 0 0
1 1 0
2 0 0
0 0 0
Correct: 8
WRONG: 7

5
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 1
0 0 2 0
0 0 0 0
Correct: 17
WRONG: 16

5
2 0 0 0
0 0 1 0
1 0 0 0
1 1 0 0
0 0 0 0
Correct: 16
WRONG: 14

4
2 2 0
1 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
Correct: 22
WRONG: 20

ldg1291 3년 전 0

아 감사합니다 dfs(i+1)을 했어야 했는데 dfs(i+1+1)을 하고 있었네요..

아이고 부끄러워라;;

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

문제

문제

출처

ICPC

어느 부분에서 틀렸는지 알 수 있을까요??

ldg1291 3년 전 0

ldg1291 3년 전 0

jh05013 3년 전 0

jh05013 3년 전 0

ldg1291 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말