글 읽기 - 왜 틀린걸까요?ㅠㅠ

enoch9 3년 전 0

게시판 반례들도 포함하여 돌려봤는데 답이 맞습니다.. 어느 부분을 놓쳤는지가 궁금합니다!
#if 1
#include <cstdio>
#include <cstring>
#include <algorithm>
int n, m,ax, ay, bx, by, minn = 987654321;
char a[15][15];

int mup() {
	//printf("move up\n");
	bool tmp = false;
	int orgax = ax, orgbx = bx;
	if (ay == by) {
		tmp = true;
	}
	while (bx - 1 >= 0) {
		if (a[bx - 1][by] == 'O') return -1;
		if (a[bx - 1][by] == '#') break;
		bx--;
	}
	while (ax - 1 >= 0) {
		if (a[ax - 1][ay] == 'O') return 1;
		if (a[ax - 1][ay] == '#') break;
		if (ax - 1 == bx && ay == by) break;
		ax--;
	}
	if (tmp) { 
		//#
		//a
		//b 처럼 생겼는데 코드 상 겹친 경우
		if (ax == bx && orgbx > orgax) bx++; 
		else if (ax > bx && orgbx > orgax) {
			int tmp = ax;
			ax = bx;
			bx = tmp;
		}
	}
	return 0;
}

int mdown() {
	//printf("move down\n");
	bool tmp = false;
	int orgax = ax, orgbx = bx;
	if (ay == by) {
		tmp = true;
	}
	while (bx + 1 < n) {
		if (a[bx + 1][by] == 'O') return -1;
		if (a[bx + 1][by] == '#') break;
		bx++;
	}
	while (ax + 1 < n) {
		if (a[ax + 1][ay] == 'O') return 1;
		if (a[ax + 1][ay] == '#') break;
		if (ax + 1 == bx && ay == by) break;
		ax++;
	}
	if (tmp) {
		//b
		//a
		//# 처럼 생겼는데 코드 상 겹친 경우
		if (ax == bx && orgbx < orgax) bx--;
		else if (ax < bx && orgbx < orgax) {
			int tmp = ax;
			ax = bx;
			bx = tmp;
		}

	}
	return 0;
}
int mleft() {
	//printf("moveleft\n");
	bool tmp = false;
	int orgay = ay, orgby = by;
	if (ax == bx) {
		tmp = true;
	}
	while (by - 1 >=0) {
		if (a[bx][by - 1] == 'O') return -1;
		if (a[bx][by - 1] == '#') break;
		by--;
	}
	while (ay - 1 >= 0) {
		if (a[ax][ay - 1] == 'O') {
			//printf("a[%d][%d] = %c\n", ax, ay - 1, a[ax][ay - 1]);
			return 1;
		}
		if (a[ax][ay - 1] == '#') break;
		if (ax == bx && ay - 1 == by) break;
		ay--;
	}
	if (tmp) {
		//# a b 처럼 생겼는데 코드 상 겹친 경우
		if (ay == by && orgby > orgay) by++;
		else if (ay > by && orgby > orgay) {
			int tmp = ay;
			ay = by;
			by = tmp;
		}
	}
	return 0;
}
int mright() {
	//printf("moveright\n");
	bool tmp = false;
	int orgay = ay, orgby = by;
	if (ax == bx) {
		tmp = true;
	}
	while (by + 1 < m) {
		if (a[bx][by + 1] == 'O') return -1;
		if (a[bx][by + 1] == '#') break;
		by++;
	}
	while (ay + 1 < m) {
		if (a[ax][ay + 1] == 'O') return 1;
		if (a[ax][ay + 1] == '#') break;
		if (ax == bx && ay + 1 == by) break;
		ay++;
	}
	if (tmp) {
		//b a #
		//a
		//# 처럼 생겼는데 코드 상 겹친 경우
		if (ay == by && orgby < orgay) by--;
		else if (ay < by && orgby < orgay) {
			int tmp = ay;
			ay = by;
			by = tmp;
		}
	}
	return 0;
}
void input() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0;j < m; j++) {
			scanf(" %c", &a[i][j]);
			if (a[i][j] == 'R') {
				ax = i;
				ay = j;
				a[i][j] = '.';
			}
			else if (a[i][j] == 'B') {
				bx = i;
				by = j;
				a[i][j] = '.';
			}
		}
	}
}

//void show() {
//	for (int i = 0; i < n; i++) {
//		for (int j = 0; j < m; j++) {
//			if (ax == i && ay == j) //printf("A");
//			else if (bx == i && by == j) //printf("B");
//			else //printf("%c", a[i][j]);
//		}
//		//printf("\n");
//	}
//	//printf("\n");
//}
void dfs(int cnt, int done) {
	//printf("dfs(%d, %d)\n", cnt, done);
	//show();
	if (cnt >= 10) {
		//printf("over\n");
		return;
	}
	if (cnt >= minn) {
		//printf("over\n");
		return;
	}
	int oax = ax, oay = ay, obx = bx, oby = by;
	
	int m = 0;
	if (done != 1) {
		m = mup();
		if (m == 1) {
			minn = (minn < cnt + 1) ? minn : cnt + 1;
			ax = oax; ay = oay; bx = obx; by = oby;
			//printf("reached\n");
			//show();
			return;
		}
		else if (m == -1) {
			ax = oax; ay = oay; bx = obx; by = oby;
			if (cnt != 0) return;
		}
		else dfs(cnt + 1, 1);
		ax = oax; ay = oay; bx = obx; by = oby;
	}

	if (done != 2) {
		m = mdown();
		if (m == 1) {
			minn = (minn < cnt + 1) ? minn : cnt + 1;
			ax = oax; ay = oay; bx = obx; by = oby;
			//printf("reached\n");
			//show();
			return;
		}
		else if (m == -1) {
			ax = oax; ay = oay; bx = obx; by = oby;
			if (cnt != 0) return;
		}
		else dfs(cnt + 1, 2);
		ax = oax; ay = oay; bx = obx; by = oby;
	}

	if (done != 3) {
		m = mleft();
		if (m == 1) {
			minn = (minn < cnt + 1) ? minn : cnt + 1;
			ax = oax; ay = oay; bx = obx; by = oby;
			//printf("reached\n");
			//show();
			return;
		}
		else if (m == -1) {
			ax = oax; ay = oay; bx = obx; by = oby;
			if (cnt != 0) return;
		}
		else dfs(cnt + 1, 3);
		ax = oax; ay = oay; bx = obx; by = oby;
	}

	if (done != 4) {
		m = mright();
		if (m == 1) {
			minn = (minn < cnt + 1) ? minn : cnt + 1;
			ax = oax; ay = oay; bx = obx; by = oby;
			//printf("reached\n");
			//show();
			return;
		}
		else if (m == -1) {
			ax = oax; ay = oay; bx = obx; by = oby;
			if (cnt != 0) return;
		}
		else dfs(cnt + 1, 4);
		ax = oax; ay = oay; bx = obx; by = oby;
	}

}
int main() {
	input();
	dfs(0,0);
	if (minn == 987654321) printf("-1");
	else printf("%d\n", minn);
}

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

문제

출처

ICPC

왜 틀린걸까요?ㅠㅠ

enoch9 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
