글 읽기 - 테스트케이스는 다 맞는데 뭐가 틀린지 모르겠습니다 ㅠㅠ

kebee95 4년 전 0

제가 미처 빠트린 부분이 있을까요...?

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct bid {
	int ry, rx, by, bx, count;
};

bid start;
int N, M;
char map[10][11];
const int dy[] = { -1,1,0,0 }, dx[] = { 0,0,-1,1 };

int bfs() {
	int ans = -1;
	bool visited[10][10][10][10] = { 0, };
	queue<bid> q;
	q.push(start);
	visited[start.ry][start.rx][start.by][start.bx] = true;
	while (!q.empty()) {
		bid cur = q.front();
		q.pop();
		if (cur.ry == cur.by && cur.rx == cur.bx) break;

		if (cur.count > 10) break;

		if (map[cur.ry][cur.rx] == 'O' && map[cur.by][cur.bx] != '0') {
			ans = cur.count;
			break;
		}
		
		for (int dir = 0; dir < 4; dir++) {
			int next_ry = cur.ry;
			int next_rx = cur.rx;
			int next_by = cur.by;
			int next_bx = cur.bx;
			while (1) {
				if (map[next_ry][next_rx] != '#' && map[next_ry][next_rx] != 'O') {
					next_ry += dy[dir], next_rx += dx[dir];
				}
				else {
					if (map[next_ry][next_rx] == '#') {
						next_ry -= dy[dir], next_rx -= dx[dir];
					}
					break;
				}
			}

			while (1) {
				if (map[next_by][next_bx] != '#' && map[next_by][next_bx] != 'O') {
					next_by += dy[dir], next_bx += dx[dir];
				}
				else {
					if (map[next_by][next_bx] == '#') {
						next_by -= dy[dir], next_bx -= dx[dir];
					}
					break;
				}
			}

			if (next_ry == next_by && next_rx == next_bx) {
				if (map[next_ry][next_rx] != 'O') {
					int r_dist = abs(cur.ry - next_ry) + abs(cur.rx - next_rx);
					int b_dist = abs(cur.by - next_by) + abs(cur.bx - next_bx);
					if (r_dist > b_dist) {
						next_ry -= dy[dir], next_rx -= dx[dir];
					}
					else
						next_by -= dy[dir], next_bx -= dx[dir];
				}
				
			}

			if (!visited[next_ry][next_rx][next_by][next_bx]) {
				visited[next_ry][next_rx][next_by][next_bx] = true;
				bid next;
				next.ry = next_ry;
				next.rx = next_rx;
				next.by = next_by;
				next.bx = next_bx;
				next.count = cur.count + 1;
				q.push(next);
			}



		}
	}
	return ans;
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++)
		scanf("%s", &map[i]);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 'R') {
				start.ry = i, start.rx = j;
			}
			if (map[i][j] == 'B') {
				start.by = i, start.bx = j;
			}
		}
	}
	start.count = 0;
	int ret = bfs();
	printf("%d\n", ret);
	return 0;
}

tony9402 3년 전 1

반례 드립니다.

9 5
#####
##.##
#.R.#
#.#.#
#..##
#.B##
#.#O#
#...#
#####

answer : 9

9 5
#####
#...#
#.###
#..R#
#.###
#.B.#
#O.##
##..#
#####

answer : 3

6 6
######
##...#
#B..O#
#.##.#
###R.#
######

answer : 3

5 8
########
#..#...#
#R....B#
#.####O#
########

answer : 6

5 8
########
##..B.R#
#.....##
##...O.#
########

answer : 6

10 5
#####
#.###
##.##
#...#
#.#B#
#R..#
#.#O#
#####
##.##
#####

answer : 4

8 6
######
####.#
#.#B.#
#..R.#
#..O.#
##.#.#
#..###
######

answer : 4

8 6
######
#....#
##.###
#O...#
###B##
#R..##
##...#
######

answer : 4

5 8
########
###..#.#
#.R.B.##
#.#O...#
########

answer : 4

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

문제

문제

출처

ICPC

테스트케이스는 다 맞는데 뭐가 틀린지 모르겠습니다 ㅠㅠ

kebee95 4년 전 0

tony9402 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말