만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

포켓몬 얼음 미로

면접 대비

시간 제한2초메모리 제한512 MB

요약
얼음 칸을 미끄러지는 이동은 한 번의 이동으로 셉니다. 각 칸에서 목표 칸까지 필요한 최소 이동 횟수를 구하고, 도달할 수 없으면 -1을 출력합니다.
난이도

보통10점 중 5점

유형
BFS, 그래프, 최단 경로, 행렬
정답자
아직 제출이 없습니다

문제

당신은 다음 포켓몬 시리즈의 레벨 디자이너로 고용되었습니다. 게임 이름은 Ice와 Fire입니다. 두 게임 중 첫 번째인 Ice에서 플레이어는 얼음 동굴의 미로를 통과해야 합니다. 동굴은 격자로 되어 있고, 각 칸은 얼음, 자갈, 장애물 중 하나입니다.

플레이어는 한 칸에서 출발해 상하좌우 네 방향 중 하나로 여러 번 이동합니다. 미로는 다음과 같이 동작합니다. 플레이어가 들어가려는 칸이 장애물이면 플레이어는 움직이지 않습니다. 들어가려는 칸이 자갈이면 플레이어는 그 칸으로 이동해 멈춥니다. 들어가려는 칸이 얼음이면 플레이어는 먼저 그 칸으로 옮겨진 뒤, 같은 방향으로 같은 과정을 반복합니다. 플레이어는 장애물에 부딪히거나 자갈 칸에 닿을 때까지 얼음 위를 미끄러집니다. 얼음 위를 미끄러지는 것은 한 번의 이동으로 셉니다.

미로에는 목표 칸이 있습니다. 출발 칸은 아직 정하지 않았습니다. 레벨이 너무 쉽지 않도록, 출발 칸에서 목표 칸까지 가는 데 필요한 이동 횟수가 충분히 커야 합니다.

미로의 각 칸에서 목표 칸까지 가는 데 필요한 최소 이동 횟수를 계산해 주세요. 얼음 위를 미끄러지는 한 번의 이동으로 여러 칸을 지나갈 수 있습니다.

입력

첫 줄에 두 정수 3≤C≤10003 \le C \le 1000과 3≤R≤10003 \le R \le 1000이 주어집니다. 이는 미로의 열 수와 행 수입니다. 다음 RR개의 줄에는 각각 CC개의 문자로 미로의 칸이 주어집니다.

  • .은 자갈 칸입니다.
  • #은 장애물 칸입니다.
  • _은 얼음 칸입니다.
  • M은 목표 칸입니다. 자갈 칸이기도 합니다.

미로의 가장자리는 항상 장애물 칸으로 둘러싸여 있습니다.

출력

RR개의 줄을 출력합니다. 각 줄에는 CC개의 정수가 있으며, 그 칸에서 목표 칸까지 필요한 최소 이동 횟수를 나타냅니다. 목표 칸에 도달할 수 없는 칸에는 −1-1을 출력합니다.

예제2

  1. 예제 1

    입력
    5 6
#####
#...#
#_###
#_M.#
#__.#
#####
    예상 출력
    -1 -1 -1 -1 -1
-1 4 5 6 -1
-1 4 -1 -1 -1
-1 1 0 1 -1
-1 3 1 2 -1
-1 -1 -1 -1 -1

  2. 예제 2

    입력
    5 6
#####
##__#
##__#
##M_#
##_##
#####
    예상 출력
    -1 -1 -1 -1 -1
-1 -1 1 2 -1
-1 -1 1 2 -1
-1 -1 0 1 -1
-1 -1 1 -1 -1
-1 -1 -1 -1 -1