글 읽기 - 반례를 찾아주시면 감사하겠습니다.

skyjpower 5년 전 0

기본 예시나 여러 질문글에 있는 예시를 넣어보고 혼자서도 찾아보려 했는데 찾지 못하였습니다ㅠ

찾아주시면 정말 감사하겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#define SIZE 12
#define INF 1000000000 

using namespace std;
char map[SIZE][SIZE];
// 빨간 구슬 파란 구슬 도착점 좌표 
int Rs_x, Rs_y, Bs_x, Bs_y, E_x, E_y;
int n, m;
bool Rflag = false;
bool Bflag = false;
int iMin = INF;

void swap(char *a, char *b) {
	char temp = *a;
	*a = *b;
	*b = temp;
}

int rolling(int x, int y, int dir) {
	int temp;
	// 위로 
	if (dir == 0) {
		for (temp = x; map[temp - 1][y] == '.' || map[temp - 1][y] == 'O'; temp--) {
			if (map[temp][y] == 'O') break;
		}
		return temp;
	}
	// 아래로 
	else if (dir == 1) {
		for (temp = x; map[temp + 1][y] == '.' || map[temp + 1][y] == 'O'; temp++) {
			if (map[temp][y] == 'O') break;
		}
		return temp;
	}
	// 왼쪽으로 
	else if (dir == 2) {
		for (temp = y; map[x][temp - 1] == '.' || map[x][temp - 1] == 'O'; temp--) {
			if (map[x][temp] == 'O') break;
		}
		return temp;
	}
	// 오른쪽으로 
	else if (dir == 3) {
		for (temp = y; map[x][temp + 1] == '.' || map[x][temp + 1] == 'O'; temp++) {
			if (map[x][temp] == 'O') break;
		}
		return temp;
	}
}

void dfs(int rx, int ry, int bx, int by, int iNum, int turn) {
	if (iNum > 10) return;
	if (bx == E_x && by == E_y) return;
	// 파란공은 들어가지 않고,  
	if (rx == E_x && ry == E_y) {
		if (iMin > iNum) iMin = iNum;
		return;
	}

	for (int i = 0; i<4; i++) {
		// 반대 방향으로 도는 것을 막는다.
		if (turn == 0 && i == 1) continue;
		if (turn == 1 && i == 0) continue;
		if (turn == 2 && i == 3) continue;
		if (turn == 3 && i == 2) continue;

		int nrx, nry, nbx, nby;
		char prevR, nextR, prevB, nextB;
		if (i == 0) {
			// 레드구슬부터 굴리기 
			if (rx < bx) {
				// 레드 구슬 굴리기  
				nrx = rolling(rx, ry, i);
				if (nrx != rx) {
					if (map[nrx][ry] == '.') {
						nextR = 'R';
						prevR = '.';
					}
					else {
						nextR = 'O';
						prevR = '.';
					}
					swap(&map[nrx][ry], &nextR);
					swap(&map[rx][ry], &prevR);
				}
				
				// 파랑 구슬 굴리기 
				nbx = rolling(bx, by, i);
				if (nbx != bx) {
					if (map[nbx][by] == '.') {
						nextB = 'B';
						prevB = '.';
					}
					else {
						nextB = 'O';
						prevB = '.';
					}
					swap(&map[nbx][by], &nextB);
					swap(&map[bx][by], &prevB);
				}
				
				// 움직임이 전혀 없다면
				if (nrx == rx && nbx == bx) continue;

				dfs(nrx, ry, nbx, by, iNum + 1, i);
				swap(&map[nrx][ry], &nextR);
				swap(&map[rx][ry], &prevR);
				swap(&map[nbx][by], &nextB);
				swap(&map[bx][by], &prevB);
			}
			else {
				nbx = rolling(bx, by, i);
				if (bx != nbx) {
					if (map[nbx][by] == '.') {
						nextB = 'B';
						prevB = '.';
					}
					else {
						nextB = 'O';
						prevB = '.';
					}
					swap(&map[nbx][by], &nextB);
					swap(&map[bx][by], &prevB);
				}

				nrx = rolling(rx, ry, i);
				if (nrx != rx) {
					if (map[nrx][ry] == '.') {
						nextR = 'R';
						prevR = '.';
					}
					else {
						nextR = 'O';
						prevR = '.';
					}
					swap(&map[nrx][ry], &nextR);
					swap(&map[rx][ry], &prevR);
				}
				// 움직임이 전혀 없다면
				if (nrx == rx && nbx == bx) continue;

				dfs(nrx, ry, nbx, by, iNum + 1, i);
				swap(&map[nrx][ry], &nextR);
				swap(&map[rx][ry], &prevR);
				swap(&map[nbx][by], &nextB);
				swap(&map[bx][by], &prevB);
			}
		}
		// 아래로 
		else if (i == 1) {
			// 레드구슬부터 굴리기 
			if (rx > bx) {
				// 레드 구슬 굴리기  
				nrx = rolling(rx, ry, i);
				if (nrx != rx) {
					if (map[nrx][ry] == '.') {
						nextR = 'R';
						prevR = '.';
					}
					else {
						nextR = 'O';
						prevR = '.';
					}
					swap(&map[nrx][ry], &nextR);
					swap(&map[rx][ry], &prevR);
				}
				
				// 파랑 구슬 굴리기 
				nbx = rolling(bx, by, i);
				if (nbx != bx) {
					if (map[nbx][by] == '.') {
						nextB = 'B';
						prevB = '.';
					}
					else {
						nextB = 'O';
						prevB = '.';
					}
					swap(&map[nbx][by], &nextB);
					swap(&map[bx][by], &prevB);

				}
				// 움직임이 전혀 없다면
				if (nrx == rx && nbx == bx) continue;
				
				dfs(nrx, ry, nbx, by, iNum + 1, i);

				swap(&map[nrx][ry], &nextR);
				swap(&map[rx][ry], &prevR);
				swap(&map[nbx][by], &nextB);
				swap(&map[bx][by], &prevB);
			}
			else {
				nbx = rolling(bx, by, i);
				if (nbx != bx) {
					if (map[nbx][by] == '.') {
						nextB = 'B';
						prevB = '.';
					}
					else {
						nextB = 'O';
						prevB = '.';
					}
					swap(&map[nbx][by], &nextB);
					swap(&map[bx][by], &prevB);
				}
				

				nrx = rolling(rx, ry, i);
				if (nrx != rx) {
					if (map[nrx][ry] == '.') {
						nextR = 'R';
						prevR = '.';
					}
					else {
						nextR = 'O';
						prevR = '.';
					}
					swap(&map[nrx][ry], &nextR);
					swap(&map[rx][ry], &prevR);
				}
				// 움직임이 전혀 없다면
				if (nrx == rx && nbx == bx) continue;
				
				dfs(nrx, ry, nbx, by, iNum + 1, i);

				swap(&map[nrx][ry], &nextR);
				swap(&map[rx][ry], &prevR);
				swap(&map[nbx][by], &nextB);
				swap(&map[bx][by], &prevB);
			}
		}
		else if (i == 2) {
			// 빨간 구슬 먼저 
			if (ry < by) {
				nry = rolling(rx, ry, i);
				if (nry != ry) {
					if (map[rx][nry] == '.') {
						nextR = 'R';
						prevR = '.';
					}
					else {
						nextR = 'O';
						prevR = '.';
					}
					swap(&map[rx][ry], &prevR);
					swap(&map[rx][nry], &nextR);
				}
				
				nby = rolling(bx, by, i);
				if (nby != by) {
					if (map[bx][nby] == '.') {
						nextB = 'B';
						prevB = '.';
					}
					else {
						nextB = 'O';
						prevB = '.';
					}
					swap(&map[bx][by], &prevB);
					swap(&map[bx][nby], &nextB);
				}
				// 움직임이 전혀 없다면
				if (nry == ry && nby == by) continue;
				
				dfs(rx, nry, bx, nby, iNum + 1, i);

				swap(&map[rx][ry], &prevR);
				swap(&map[rx][nry], &nextR);
				swap(&map[bx][by], &prevB);
				swap(&map[bx][nby], &nextB);
			}
			// 파란 구슬 먼저 
			else {
				nby = rolling(bx, by, i);
				if (nby != by) {
					if (map[bx][nby] == '.') {
						nextB = 'B';
						prevB = '.';
					}
					else {
						nextB = 'O';
						prevB = '.';
					}
					swap(&map[bx][by], &prevB);
					swap(&map[bx][nby], &nextB);

				}
				
				nry = rolling(rx, ry, i);
				if (nry != ry) {
					if (map[rx][nry] == '.') {
						nextR = 'R';
						prevR = '.';
					}
					else {
						nextR = 'O';
						prevR = '.';
					}
					swap(&map[rx][ry], &prevR);
					swap(&map[rx][nry], &nextR);
				}
				if (nry == ry && nby == by) continue;

				dfs(rx, nry, bx, nby, iNum + 1, i);

				swap(&map[rx][ry], &prevR);
				swap(&map[rx][nry], &nextR);
				swap(&map[bx][by], &prevB);
				swap(&map[bx][nby], &nextB);
			}
		}
		else if (i == 3) {
			if (ry > by) {
				nry = rolling(rx, ry, i);
				if (nry != ry) {
					if (map[rx][nry] == '.') {
						nextR = 'R';
						prevR = '.';
					}
					else {
						nextR = 'O';
						prevR = '.';
					}
					swap(&map[rx][ry], &prevR);
					swap(&map[rx][nry], &nextR);

				}
				
				nby = rolling(bx, by, i);
				if (nby != by) {
					if (map[bx][nby] == '.') {
						nextB = 'B';
						prevB = '.';
					}
					else {
						nextB = 'O';
						prevB = '.';
					}
					swap(&map[bx][by], &prevB);
					swap(&map[bx][nby], &nextB);

				}
				if (nry == ry && nby == by) continue;
				
				dfs(rx, nry, bx, nby, iNum + 1, i);

				swap(&map[rx][ry], &prevR);
				swap(&map[rx][nry], &nextR);
				swap(&map[bx][by], &prevB);
				swap(&map[bx][nby], &nextB);
			}
			// 파란 구슬 먼저 
			else {
				nby = rolling(bx, by, i);
				if (nby != by) {
					if (map[bx][nby] == '.') {
						nextB = 'B';
						prevB = '.';
					}
					else {
						nextB = 'O';
						prevB = '.';
					}
					swap(&map[bx][by], &prevB);
					swap(&map[bx][nby], &nextB);
				}

				nry = rolling(rx, ry, i);
				if (nry != ry) {
					if (map[rx][nry] == '.') {
						nextR = 'R';
						prevR = '.';
					}
					else {
						nextR = 'O';
						prevR = '.';
					}
					swap(&map[rx][ry], &prevR);
					swap(&map[rx][nry], &nextR);
				}
				if (nry == ry && nby == by) continue;

				dfs(rx, nry, bx, nby, iNum + 1, i);

				swap(&map[rx][ry], &prevR);
				swap(&map[rx][nry], &nextR);
				swap(&map[bx][by], &prevB);
				swap(&map[bx][nby], &nextB);
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i<n; i++) {
		scanf("%s", map[i]);
		for (int j = 0; j<m; j++) {
			if (map[i][j] == 'R') {
				Rs_x = i;
				Rs_y = j;
			}
			else if (map[i][j] == 'B') {
				Bs_x = i;
				Bs_y = j;
			}
			else if (map[i][j] == 'O') {
				E_x = i;
				E_y = j;
			}
		}
	}
	dfs(Rs_x, Rs_y, Bs_x, Bs_y, 0, -1);
	printf("%d\n", iMin == INF ? -1 : iMin);

	return 0;
}

djm03178 5년 전 0

반례 드립니다.

10 10
##########
#...#....#
#.#...##.#
#..#....##
#......#.#
##R....#.#
#.......##
#..###...#
##...#B#O#
##########
output: 8
correct answer: 4

10 9
#########
#.......#
##..R...#
#B......#
#O#.....#
#.....#.#
#..#....#
#..#.#..#
#......##
#########
output: 7
correct answer: 6

10 9
#########
#R...B#.#
#.....#.#
#.......#
##.#....#
#....#..#
#.#....O#
##.....##
#...##..#
#########
output: 5
correct answer: 4

skyjpower 5년 전 0

문제는 dfs탐색하고 다시 본래 배열로 복귀하는 과정에서 실수가 있었네요.

덕분에 해결되었습니다. 정말 감사드립니다.

skyjpower 5년 전 0

여러 질문글들을 보았는데 랜덤 생성기(?)를 통해 예제를 만드신다고 말씀하시는 것 같더라구요.

특정 프로그램을 이용하시는건지 여쭤봐도 될까요?

djm03178 5년 전 3

직접 개발한 프로그램입니다. 뭐든지 자동으로 해주는 것은 아니고, 데이터 생성기, 맞는 코드, 틀린 코드를 넣고 실행하면 맞는 코드와 틀린 코드가 서로 다른 답을 내놓을 때까지 생성기로 데이터를 만들고 양쪽에 넣어보는 것을 반복해주는 프로그램입니다.

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

문제

문제

출처

ICPC

반례를 찾아주시면 감사하겠습니다.

skyjpower 5년 전 0

djm03178 5년 전 0

skyjpower 5년 전 0

skyjpower 5년 전 0

djm03178 5년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말