글 읽기 - bfs로는 되는데 dfs로 하니 56%에서 에러가납니다.

wldnjs95 6년 전 0

move_ball 함수와 main에 있는 것은 bfs로 짰을 때와 똑같아서 문제가 없을 것 같고
dfs함수를 저렇게 짰는데 56%에서 계속 틀렸다고 나오네요 뭐가 문제일까요?
#include <stdio.h>
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

int N, M;
int bx, by, rx, ry;
int ox, oy;
char initmap[20];
int map[20][20];
int visit[20][20][20][20];
int mincnt = 2100000000;

int move_ball(int bluex, int bluey, int redx, int redy, int cdir) {
	int i, j;
	switch (cdir) { //switch open
	case UP:
		if (bluey == redy) {
			if (bluex < redx) { //blue가 더 위쪽
				for (i = bluex; i >= 0; i--) {
					if (map[i][bluey] == -1) return 0;
					if (map[i][bluey] != 0) {
						bx = i + 1;
						by = bluey;
						break;
					}
				}

				for (i = redx; i >= bx; i--) {
					if (map[i][redy] == -1) {
						rx = i;
						ry = redy;
						break;
					}
					if (i == bx || map[i][bluey] != 0) {
						rx = i + 1;
						ry = redy;
						break;
					}
				}
			}
			else { //red가 더 위쪽
				for (i = redx; i >= 0; i--) {
					if (map[i][redy] == -1) {
						rx = i;
						ry = redy;
						break;
					}
					if (map[i][bluey] != 0) {
						rx = i + 1;
						ry = redy;
						break;
					}
				}
				for (i = bluex; i >= rx; i--) {
					if (map[i][bluey] == -1) return 0;
					if (i == rx || map[i][bluey] != 0) {
						bx = i + 1;
						by = bluey;
						break;
					}
				}
			}
		}//outer if
		else {
			for (i = redx; i >= 0; i--) {
				if (map[i][redy] == -1) {
					rx = i;
					ry = redy;
					break;
				}
				if (map[i][redy] != 0) {
					rx = i + 1;
					ry = redy;
					break;
				}
			}
			for (i = bluex; i >= 0; i--) {
				if (map[i][bluey] == -1) return 0;
				if (map[i][bluey] != 0) {
					bx = i + 1;
					by = bluey;
					break;
				}
			}
		}//outer if-else
		break;

	case RIGHT:
		if (bluex == redx) {
			if (bluey < redy) { //blue가 더 왼쪽
				for (j = redy; j < M; j++) {
					if (map[redx][j] == -1) {
						rx = redx;
						ry = j;
						break;
					}
					if (map[redx][j] != 0) {
						rx = redx;
						ry = j - 1;
						break;
					}
				}
				for (j = bluey; j <= ry; j++) {
					if (map[bluex][j] == -1) return 0;
					if (j == ry || map[bluex][j] != 0) {
						bx = bluex;
						by = j - 1;
						break;
					}
				}
			}
			else { //red가 더 왼쪽
				for (j = bluey; j < M; j++) {
					if (map[bluex][j] == -1) return 0;
					if (map[bluex][j] != 0) {
						bx = bluex;
						by = j - 1;
						break;
					}
				}
				for (j = redy; j <= by; j++) {
					if (map[redx][j] == -1) {
						rx = redx;
						ry = j;
						break;
					}
					if (j == by || map[redx][j] != 0) {
						rx = redx;
						ry = j - 1;
						break;
					}
				}
			}
		} //outer if
		else {
			for (j = redy; j < M; j++) {
				if (map[redx][j] == -1) {
					rx = redx;
					ry = j;
					break;
				}
				if (map[redx][j] != 0) {
					rx = redx;
					ry = j - 1;
					break;
				}
			}
			for (j = bluey; j < M; j++) {
				if (map[bluex][j] == -1) return 0;
				if (map[bluex][j] != 0) {
					bx = bluex;
					by = j - 1;
					break;
				}
			}
		}
		break;
	case DOWN:
		if (bluey == redy) {
			if (bluex < redx) { //blue가 더 위쪽
				for (i = redx; i < N; i++) {
					if (map[i][redy] == -1) {
						rx = i;
						ry = redy;
						break;
					}
					if (map[i][bluey] != 0) {
						rx = i - 1;
						ry = redy;
						break;
					}
				}
				for (i = bluex; i <= rx; i++) {
					if (map[i][bluey] == -1) return 0;
					if (i == rx || map[i][bluey] != 0) {
						bx = i - 1;
						by = bluey;
						break;
					}
				}
			}
			else { //red가 더 위쪽
				for (i = bluex; i < N; i++) {
					if (map[i][bluey] == -1) return 0;
					if (map[i][bluey] != 0) {
						bx = i - 1;
						by = bluey;
						break;
					}
				}

				for (i = redx; i <= bx; i++) {
					if (map[i][redy] == -1) {
						rx = i;
						ry = redy;
						break;
					}
					if (i == bx || map[i][bluey] != 0) {
						rx = i - 1;
						ry = redy;
						break;
					}
				}
			}
		} //outer if
		else {
			for (i = redx; i < N; i++) {
				if (map[i][redy] == -1) {
					rx = i;
					ry = redy;
					break;
				}
				if (map[i][redy] != 0) {
					rx = i - 1;
					ry = redy;
					break;
				}
			}
			for (i = bluex; i < N; i++) {
				if (map[i][bluey] == -1) return 0;
				if (map[i][bluey] != 0) {
					bx = i - 1;
					by = bluey;
					break;
				}
			}
		}
		break;
	case LEFT:
		if (bluex == redx) {
			if (bluey < redy) { //blue가 더 왼쪽
				for (j = bluey; j >= 0; j--) {
					if (map[bluex][j] == -1) return 0;
					if (map[bluex][j] != 0) {
						bx = bluex;
						by = j + 1;
						break;
					}
				}
				for (j = redy; j >= by; j--) {
					if (map[redx][j] == -1) {
						rx = redx;
						ry = j;
						break;
					}
					if (j == by || map[redx][j] != 0) {
						rx = redx;
						ry = j + 1;
						break;
					}
				}
			}
			else { //red가 더 왼쪽
				for (j = redy; j >= 0; j--) {
					if (map[redx][j] == -1) {
						rx = redx;
						ry = j;
						break;
					}
					if (map[redx][j] != 0) {
						rx = redx;
						ry = j + 1;
						break;
					}
				}
				for (j = bluey; j >= ry; j--) {
					if (map[bluex][j] == -1) return 0;
					if (j == ry || map[bluex][j] != 0) {
						bx = bluex;
						by = j + 1;
						break;
					}
				}
			}
		}
		else {
			for (j = redy; j >= 0; j--) {
				if (map[redx][j] == -1) {
					rx = redx;
					ry = j;
					break;
				}
				if (map[redx][j] != 0) {
					rx = redx;
					ry = j + 1;
					break;
				}
			}
			for (j = bluey; j >= 0; j--) {
				if (map[bluex][j] == -1) return 0;
				if (map[bluex][j] != 0) {
					bx = bluex;
					by = j + 1;
					break;
				}
			}
			break;
		} 
	}//switch end
	return 1;
}//moveball end

void dfs(int bluex,int bluey, int redx, int redy, int dep) {
	int dir;
	if (dep >=mincnt) return;
	if (redx == ox && redy == oy) {
		if (mincnt > dep) mincnt = dep;
	}
	if (dep >10) return;
	for (dir = 0; dir < 4; dir++) {
		if (move_ball(bluex, bluey, redx, redy, dir)) {
				dfs(bx, by, rx, ry, dep + 1);
		}
	}
}
int main(void) {
	int i, j;
	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++) {
		scanf("%s", &initmap);
		for (j = 0; j<M; j++) {
			if (initmap[j] == '#') {
				map[i][j] = 1;
			}
			else if (initmap[j] == 'O') {
				ox = i;
				oy = j;
				map[i][j] = -1;
			}
			else if (initmap[j] == 'B') {
				bx = i;
				by = j;
			}
			else if (initmap[j] == 'R') {
				rx = i;
				ry = j;
			}
		}//inner for
	}//outer for
	dfs(bx, by, rx, ry, 0);
	if (mincnt > 10000) mincnt = -1;
	printf("%d\n", mincnt);
	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

bfs로는 되는데 dfs로 하니 56%에서 에러가납니다.

wldnjs95 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
