7128 : 시뮬레이션 — 구슬 탈출
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N × M 미로 상자에서 빨간 구슬과 파란 구슬을 굴려 빨간 구슬만 구멍 O를 통해 탈출시키는 퍼즐입니다.
- 벽(#), 빈칸(.), 구멍(O)이 존재하며 상자를 상, 하, 좌, 우 네 방향으로 기울일 수 있습니다.
- 구슬들은 장애물(벽 또는 다른 구슬)에 부딪힐 때까지 그 방향으로 끝까지 미끄러집니다.
- 빨간 구슬이 구멍에 빠지면 성공, 파란 구슬이 빠지면 실패입니다. (동시에 빠져도 실패입니다.)
최소 몇 번 상자를 기울여서 빨간 구슬을 탈출시킬 수 있는지 구하십시오. (10회 이하로 탈출할 수 없으면 -1을 출력합니다.)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
- 벽(#), 빈칸(.), 구멍(O)이 존재하며 상자를 상, 하, 좌, 우 네 방향으로 기울일 수 있습니다.
- 구슬들은 장애물(벽 또는 다른 구슬)에 부딪힐 때까지 그 방향으로 끝까지 미끄러집니다.
- 빨간 구슬이 구멍에 빠지면 성공, 파란 구슬이 빠지면 실패입니다. (동시에 빠져도 실패입니다.)
최소 몇 번 상자를 기울여서 빨간 구슬을 탈출시킬 수 있는지 구하십시오. (10회 이하로 탈출할 수 없으면 -1을 출력합니다.)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 공백으로 구분되어 주어집니다. (3 ≤ N, M ≤ 10)
둘째 줄부터 N개의 줄에 미로의 모양이 주어집니다.
둘째 줄부터 N개의 줄에 미로의 모양이 주어집니다.
출력 설명
빨간 구슬만 탈출시키는 최소 기울이기 횟수를 출력합니다. 10회 이내로 불가능하면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
#####
#..B#
#.#.#
#RO.#
#####
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
BFS 탐색을 수행하되, 큐의 원소로
(rx, ry, bx, by, depth)를 관리합니다. 두 구슬이 동시에 움직이므로 이동 후 같은 칸에 도달한 경우 더 멀리서 굴러온 구슬의 위치를 한 칸 뒤로 조정해야 합니다.