글 읽기 - 예제는 다 맞는데 제출하면 틀립니다..

leeseiyoun 5년 전 0

왜이런걸까요?

반례나 팁 주시면 감사하겠습니다.

#include <iostream>
#include <queue>

#define MIN_MAP_SIZE 3
#define MAX_MAP_SIZE 8
#define START_WALL_COUNT 3

enum MapType {
	EMPTY = 0, WALL = 1, VIRUS = 2
};

int N;
int M;
MapType map[MAX_MAP_SIZE][MAX_MAP_SIZE];
int ans = 0;

using namespace std;
queue<pair<int, int>> virusPos;

int GetSafeZone() {
	int result = 0;
	queue<pair<int, int>> tmpPos;
	tmpPos = virusPos;
	while(tmpPos.size() > 0) {
		int nr = tmpPos.front().first;
		int nc = tmpPos.front().second;

		while (nr >= 0) {
			if (map[nr][nc] == MapType::EMPTY) {
				map[nr][nc] = MapType::VIRUS;
				tmpPos.push(make_pair(nr, nc));
			}
			if (map[nr][nc] == MapType::WALL)
				break;
			--nr;
		}
		nr = tmpPos.front().first;
		nc = tmpPos.front().second;

		while (nc >= 0) {
			if (map[nr][nc] == MapType::EMPTY) {
				map[nr][nc] = MapType::VIRUS;
				tmpPos.push(make_pair(nr, nc));
			}
			if (map[nr][nc] == MapType::WALL)
				break;
			--nc;
		}
		nr = tmpPos.front().first;
		nc = tmpPos.front().second;

		while (nr < N) {
			if (map[nr][nc] == MapType::EMPTY) {
				map[nr][nc] = MapType::VIRUS;
				tmpPos.push(make_pair(nr, nc));
			}
			if (map[nr][nc] == MapType::WALL)
				break;
			++nr;
		}
		nr = tmpPos.front().first;
		nc = tmpPos.front().second;

		while (nc < M) {
			if (map[nr][nc] == MapType::EMPTY) {
				map[nr][nc] = MapType::VIRUS;
				tmpPos.push(make_pair(nr, nc));
			}
			if (map[nr][nc] == MapType::WALL)
				break;
			++nc;
		}
		tmpPos.pop();
	}
	for (int n = 0; n < N; ++n) {
		for (int m = 0; m < M; ++m) {
			if (map[n][m] == MapType::EMPTY)
				++result;
		}
	}
	return result;
}

void execute(int r, int c, int leftWallCount) {
	if (leftWallCount == 0) {
		int tmp = GetSafeZone();
		ans = ans > tmp ? ans : tmp;
		return;
	}
	MapType tmpMap[MAX_MAP_SIZE][MAX_MAP_SIZE];
	for (int n = 0; n < N; ++n)
		for (int m = 0; m < M; ++m)
			tmpMap[n][m] = map[n][m];
	MapType curMapType = map[r][c];

	int nextC = (c + 1) < M ? (c + 1) : 0;
	int nextR = nextC != 0 ? r : r + 1;
	if (nextR < N) {
		if (curMapType == MapType::EMPTY) {
			execute(nextR, nextC, leftWallCount);
			for (int n = 0; n < N; ++n)
				for (int m = 0; m < M; ++m)
					map[n][m] = tmpMap[n][m];
			map[r][c] = MapType::WALL;
			execute(nextR, nextC, leftWallCount - 1);
		}
		else {
			for (int n = 0; n < N; ++n)
				for (int m = 0; m < M; ++m)
					map[n][m] = tmpMap[n][m];
			execute(nextR, nextC, leftWallCount);
		}
	}
}

int main() {
	cin >> N >> M;
	for (int n = 0; n < N; ++n) {
		for (int m = 0; m < M; ++m) {
			int tmp = 0;
			cin >> tmp;
			map[n][m] = (MapType)tmp;
			if (map[n][m] == MapType::VIRUS)
				virusPos.push(make_pair(n, m));
		}
	}
	execute(0, 0, START_WALL_COUNT);
	cout << ans << endl;
	return 0;
}

ryute 5년 전 0

질문 전에 질문 게시판 공지사항을 읽으라고 나올텐데, 혹시 질문게시판 공지사항은 읽어보셨나요? 읽지 않으셨다면 먼저 읽어보는것을 강력히 추천드립니다.

jh05013 5년 전 2

랜덤으로 만든 반례 드립니다.

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

8
0 1 0 1 0 1 0
0 0 0 1 0 1 0
1 0 1 0 0 0 1
0 0 0 0 1 0 0
0 0 1 0 0 0 0
0 1 1 0 1 0 0
0 0 0 0 0 0 2
0 1 0 0 1 1 0
Correct: 41
WRONG: 40

6
0 0 1 1 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 1
1 0 0 2 0
Correct: 21
WRONG: 20

leeseiyoun 5년 전 0

jh05013님! 반례 감사드립니다! 첨부해주신걸로 찾아서 수정해봐야겠습니다!

leeseiyoun 5년 전 0

jh05013님 감사합니다! 덕분에 문제가 되던 부분을 찾았습니다!

100번째 줄에서 r범위를 제한시키면서 그만 마지막 벽이 제대로 계산에 포함이 안되는 문제가 있었습니다!

감사합니다~!

#include <iostream>
#include <queue>

#define MIN_MAP_SIZE 3
#define MAX_MAP_SIZE 8
#define START_WALL_COUNT 3

enum MapType {
	EMPTY = 0, WALL = 1, VIRUS = 2
};

int N;
int M;
MapType map[MAX_MAP_SIZE][MAX_MAP_SIZE];
int ans = 0;

using namespace std;
queue<pair<int, int>> virusPos;

int GetSafeZone() {
	int result = 0;
	queue<pair<int, int>> tmpPos;
	tmpPos = virusPos;
	while(tmpPos.size() > 0) {
		int nr = tmpPos.front().first;
		int nc = tmpPos.front().second;

		while (nr >= 0) {
			if (map[nr][nc] == MapType::EMPTY) {
				map[nr][nc] = MapType::VIRUS;
				tmpPos.push(make_pair(nr, nc));
			}
			if (map[nr][nc] == MapType::WALL)
				break;
			--nr;
		}
		nr = tmpPos.front().first;
		nc = tmpPos.front().second;

		while (nc >= 0) {
			if (map[nr][nc] == MapType::EMPTY) {
				map[nr][nc] = MapType::VIRUS;
				tmpPos.push(make_pair(nr, nc));
			}
			if (map[nr][nc] == MapType::WALL)
				break;
			--nc;
		}
		nr = tmpPos.front().first;
		nc = tmpPos.front().second;

		while (nr < N) {
			if (map[nr][nc] == MapType::EMPTY) {
				map[nr][nc] = MapType::VIRUS;
				tmpPos.push(make_pair(nr, nc));
			}
			if (map[nr][nc] == MapType::WALL)
				break;
			++nr;
		}
		nr = tmpPos.front().first;
		nc = tmpPos.front().second;

		while (nc < M) {
			if (map[nr][nc] == MapType::EMPTY) {
				map[nr][nc] = MapType::VIRUS;
				tmpPos.push(make_pair(nr, nc));
			}
			if (map[nr][nc] == MapType::WALL)
				break;
			++nc;
		}
		tmpPos.pop();
	}
	for (int n = 0; n < N; ++n) {
		for (int m = 0; m < M; ++m) {
			if (map[n][m] == MapType::EMPTY)
				++result;
		}
	}
	return result;
}

void execute(int r, int c, int leftWallCount) {
	if (leftWallCount == 0) {
		int tmp = GetSafeZone();
		ans = ans > tmp ? ans : tmp;
		return;
	}
	if (r < 0 || c < 0 || r > N || c > M)
		return;
	MapType tmpMap[MAX_MAP_SIZE][MAX_MAP_SIZE];
	for (int n = 0; n < N; ++n)
		for (int m = 0; m < M; ++m)
			tmpMap[n][m] = map[n][m];
	MapType curMapType = map[r][c];

	int nextC = (c + 1) < M ? (c + 1) : 0;
	int nextR = nextC != 0 ? r : r + 1;
	//if (nextR < N) {

		if (curMapType == MapType::EMPTY) {
			map[r][c] = MapType::WALL;
			execute(nextR, nextC, leftWallCount - 1);
			for (int n = 0; n < N; ++n)
				for (int m = 0; m < M; ++m)
					map[n][m] = tmpMap[n][m];
		}

		execute(nextR, nextC, leftWallCount);		
	//}
}

int main() {
	cin >> N >> M;
	for (int n = 0; n < N; ++n) {
		for (int m = 0; m < M; ++m) {
			int tmp = 0;
			cin >> tmp;
			map[n][m] = (MapType)tmp;
			if (map[n][m] == MapType::VIRUS)
				virusPos.push(make_pair(n, m));
		}
	}
	execute(0, 0, START_WALL_COUNT);
	cout << ans << endl;
	return 0;
}

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

문제

문제

출처

ICPC

예제는 다 맞는데 제출하면 틀립니다..

leeseiyoun 5년 전 0

ryute 5년 전 0

jh05013 5년 전 2

leeseiyoun 5년 전 0

leeseiyoun 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말