글 읽기 - 반례 한 번만 부탁드립니다..

sce9573 4년 전 0

안녕하세요.

4577번 소코반 문제를 푸는데 문제 이해를 잘못한 것인지 아무리 생각해도 반례를 못찾겠습니다...

반례 한 번만 부탁 드려요...

감사합니다.

// 소코반

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

#define SIZE 20

using namespace std;

int R, C;
char mapOrigin[SIZE][SIZE];
char map[SIZE][SIZE];

vector<int> op;
pair<int, int> p;

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

void init() {
	op.clear();
	p = make_pair(-1, -1);
}

void displayMap(char arr[][SIZE]) {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			printf("%c", arr[i][j]);
		}
		printf("\n");
	}
}

bool isComplete() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j] == 'b') return false;
		}
	}

	return true;
}

int main() {
	int T;
	//freopen("4577.txt", "r", stdin);
	setbuf(stdout, NULL);

	char temp[100];
	int t = 1;

	while (1) {
		scanf("%d %d", &R, &C);
		if (R == 0 && C == 0) break;

		for (int i = 0; i < R; i++) {
			scanf("%s", temp);

			for (int j = 0; j < C; j++) {
				mapOrigin[i][j] = temp[j];		// .: 빈 칸, #: 벽, +: 비어있는 목표점, b: 박스, B: 목표점 위에 있는 박스, w: 캐릭터, W: 목표점 위에 있는 캐릭터
				if (mapOrigin[i][j] == 'w') p = make_pair(i, j);
			}
		}

		scanf("%s", temp);

		int j = 0;
		while (temp[j] != '\0') {
			if (temp[j] == 'U') op.push_back(0);
			else if (temp[j] == 'R') op.push_back(1);
			else if (temp[j] == 'D') op.push_back(2);
			else if (temp[j] == 'L') op.push_back(3);
			j++;
		}

		// 박스나 벽이 아닌 곳으로 이동 가능
		// 지시한 방향에 박스가 있다면 밀자. 단, 이동할 칸이 안 비어있다면 못가
		// 지시한 방향이 벽인 경우 or 박스가 있는데 박스가 이동할 칸에 다른 박스나 벽이 있는 경우 캐릭터는 이동 X
		memcpy(map, mapOrigin, sizeof(map));

		int o;
		int nextY, nextX;
		//displayMap(map);

		for (int i = 0; i < op.size(); i++) {
			o = op[i];

			nextY = p.first + dy[o];
			nextX = p.second + dx[o];

			if (nextY < 0 || nextX < 0 || nextY > R - 1 || nextX > C - 1) continue;
			if (map[nextY][nextX] == '#') continue;							// 못가

			// 빈 칸으로 갈 경우
			if (map[nextY][nextX] == '.') {
				map[nextY][nextX] = 'w';

				// 지금 player가 있는 곳이 목표점이었다면
				if (mapOrigin[p.first][p.second] == '+') map[p.first][p.second] = '+';		
				else map[p.first][p.second] = '.';			// 복구
				p.first = nextY, p.second = nextX;
			}

			// 목표점으로 갈 경우
			if (map[nextY][nextX] == '+') {
				map[nextY][nextX] = 'W';

				// 지금 player가 있는 곳이 목표점이었다면
				if (mapOrigin[p.first][p.second] == '+') map[p.first][p.second] = '+';
				else map[p.first][p.second] = '.';
				p.first = nextY, p.second = nextX;
			}

			// 박스가 있다면
			if (map[nextY][nextX] == 'b' || map[nextY][nextX] == 'B') {		// 박스가 있을 경우
				// 박스가 갈 위치
				int tempY = nextY + dy[o];
				int tempX = nextX + dx[o];

				if (tempY < 0 || tempY < 0 || tempY > R - 1 || tempY > C - 1) continue;
				if (map[tempY][tempX] == '#') continue;									// 벽이면 이동 X
				if (map[tempY][tempX] == 'b' || map[tempY][tempX] == 'B') continue;		// 박스여도 이동 X

				// 박스 push
				if (map[tempY][tempX] == '.') {
					map[tempY][tempX] = 'b';

					// player가 갈 곳이 목표점이라면
					if (mapOrigin[nextY][nextX] == '+') map[nextY][nextX] = 'W';
					else map[nextY][nextX] = 'w';

					// player가 있던 곳이 목표점이라면
					if (mapOrigin[p.first][p.second] == '+') map[p.first][p.second] = '+';
					else map[p.first][p.second] = '.';
					p.first = nextY, p.second = nextX;
				}
				
				if (map[tempY][tempX] == '+') {			// 박스가 갈 곳이 목표점이라면
					map[tempY][tempX] = 'B';

					// player가 갈 곳이 목표점이라면
					if (mapOrigin[nextY][nextX] == '+') map[nextY][nextX] = 'W';
					else map[nextY][nextX] = 'w';

					// player가 있던 곳이 목표점이라면
					if (mapOrigin[p.first][p.second] == '+') map[p.first][p.second] = '+';
					else map[p.first][p.second] = '.';
					p.first = nextY, p.second = nextX;
				}
			}

			//displayMap(map);

			if (isComplete()) break;	
		}

		if (isComplete()) {
			printf("Game %d: complete\n", t);
			displayMap(map);
		}
		else {
			printf("Game %d: incomplete\n", t);
			displayMap(map);
		}

		t++;
		init();
	}

	return 0;
}

sait2000 4년 전 0

처음에 플레이어가 타겟이 아닌 곳에 있단 말이 없는데요

sce9573 4년 전 0

@sait2000 님, 지적 감사합니다.

이와 같이 코드를 수정했는데도 여전히 '틀렸습니다.'가 나오네요...

반례가 무엇일까요....ㅠㅠㅠ

// 소코반(수정)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

#define SIZE 20

using namespace std;

int R, C;
//char mapOrigin[SIZE][SIZE];
char map[SIZE][SIZE];

vector<int> op;
pair<int, int> p;

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

void init() {
	op.clear();
	p = make_pair(-1, -1);
}

void displayMap(char arr[][SIZE]) {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			printf("%c", arr[i][j]);
		}
		printf("\n");
	}
}

bool isComplete() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j] == 'b') return false;		// 박스 수 = 목표점 수
		}
	}

	return true;
}

int main() {
	int T;
	//freopen("4577.txt", "r", stdin);
	setbuf(stdout, NULL);

	char temp[52];
	int t = 1;

	while (1) {
		scanf("%d %d", &R, &C);
		if (R == 0 && C == 0) break;

		for (int i = 0; i < R; i++) {
			scanf("%s", temp);

			for (int j = 0; j < C; j++) {
				map[i][j] = temp[j];
				//mapOrigin[i][j] = temp[j];		// .: 빈 칸, #: 벽, +: 비어있는 목표점, b: 박스, B: 목표점 위에 있는 박스, w: 캐릭터, W: 목표점 위에 있는 캐릭터
				if (map[i][j] == 'w' || map[i][j] == 'W') p = make_pair(i, j);
			}
		}

		scanf("%s", temp);

		int j = 0;
		while (temp[j] != '\0') {
			if (temp[j] == 'U') op.push_back(0);
			else if (temp[j] == 'R') op.push_back(1);
			else if (temp[j] == 'D') op.push_back(2);
			else if (temp[j] == 'L') op.push_back(3);
			j++;
		}

		// 박스나 벽이 아닌 곳으로 이동 가능
		// 지시한 방향에 박스가 있다면 밀자. 단, 이동할 칸이 안 비어있다면 못가
		// 지시한 방향이 벽인 경우 or 박스가 있는데 박스가 이동할 칸에 다른 박스나 벽이 있는 경우 캐릭터는 이동 X
		//memcpy(map, mapOrigin, sizeof(map));

		int o;
		int nextY, nextX;

		//int cnt = 0;

		for (int i = 0; i < op.size(); i++) {
			//printf("\n=== %d번째 map ===\n", cnt++);
			//displayMap(map);

			o = op[i];

			nextY = p.first + dy[o];
			nextX = p.second + dx[o];

			if (nextY < 0 || nextX < 0 || nextY > R - 1 || nextX > C - 1) continue;
			if (map[nextY][nextX] == '#') continue;							// 못가

			// player가 빈 칸으로 갈 경우
			if (map[nextY][nextX] == '.') {
				map[nextY][nextX] = 'w';

				// 지금 player가 있는 곳이 목표점이었다면
				if (map[p.first][p.second] == '+' || map[p.first][p.second] == 'W') map[p.first][p.second] = '+';
				else map[p.first][p.second] = '.';			// 복구
				p.first = nextY, p.second = nextX;
			}

			// 목표점으로 갈 경우
			if (map[nextY][nextX] == '+' || map[nextY][nextX] == 'W') {		// 박스는 아래 조건에서 처리해줄 것임
				map[nextY][nextX] = 'W';

				// 지금 player가 있는 곳이 목표점이었다면
				if (map[p.first][p.second] == '+' || map[p.first][p.second] == 'W') map[p.first][p.second] = '+';
				else map[p.first][p.second] = '.';
				p.first = nextY, p.second = nextX;
			}

			// player 갈 곳에 박스가 있다면
			if (map[nextY][nextX] == 'b' || map[nextY][nextX] == 'B') {		// 박스가 있을 경우
				// 박스가 갈 위치
				int tempY = nextY + dy[o];
				int tempX = nextX + dx[o];

				if (tempY < 0 || tempY < 0 || tempY > R - 1 || tempY > C - 1) continue;
				if (map[tempY][tempX] == '#') continue;									// 벽이면 이동 X
				if (map[tempY][tempX] == 'b' || map[tempY][tempX] == 'B') continue;		// 박스여도 이동 X

				// 박스를 빈 칸으로 민다면
				if (map[tempY][tempX] == '.') {
					map[tempY][tempX] = 'b';

					// player가 갈 곳이 목표점이라면
					if (map[nextY][nextX] == '+' || map[nextY][nextX] == 'B') map[nextY][nextX] = 'W';
					else map[nextY][nextX] = 'w';

					// player가 있던 곳이 목표점이라면
					if (map[p.first][p.second] == '+' || map[p.first][p.second] == 'W') map[p.first][p.second] = '+';
					else map[p.first][p.second] = '.';
					p.first = nextY, p.second = nextX;
				}
				
				// 박스가 갈 곳이 목표점이라면
				if (map[tempY][tempX] == '+' || map[tempY][tempX] == 'B') {		
					map[tempY][tempX] = 'B';

					// player가 갈 곳이 목표점이라면
					if (map[nextY][nextX] == '+' || map[nextY][nextX] == 'B') map[nextY][nextX] = 'W';
					else map[nextY][nextX] = 'w';

					// player가 있던 곳이 목표점이라면
					if (map[p.first][p.second] == '+' || map[p.first][p.second] == 'W') map[p.first][p.second] = '+';
					else map[p.first][p.second] = '.';
					p.first = nextY, p.second = nextX;
				}
			}

			if (isComplete()) break;	
		}

		//printf("\n=== %d번째 map ===\n", cnt++);
		//displayMap(map);

		if (isComplete()) {
			printf("Game %d: complete\n", t);
			displayMap(map);
		}
		else {
			printf("Game %d: incomplete\n", t);
			displayMap(map);
		}

		t++;
		init();
	}

	return 0;
}

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

문제

문제

출처

ICPC

반례 한 번만 부탁드립니다..

sce9573 4년 전 0

sait2000 4년 전 0

sce9573 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말