Pokémon Ice Maze

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

요약
자갈, 얼음, 장애물로 이루어진 격자에서 이동은 얼음 위를 미끄러져 멈출 때까지 진행된다. 모든 칸에서 목표까지 필요한 최소 이동 횟수를 구한다.
난이도

보통10점 중 7점

유형
그래프, BFS, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

You are hired as a level designer for the next Pokémon series, with games called Ice and Fire. For the first of these two games, players have to get through a maze in an icy cave. The cave is represented as a grid, with each square of the grid being either ice, gravel or an obstacle.

The player will start at a square, and then make a number of moves, each move represented by one of the four cardinal directions. The maze behaves in the following way. Assume that the square the player is trying to move into is an obstacle. In this case, the player does not move. If the square the player is moving into is gravel, the player successfully moves to the square and will stand still on the square. If the square is ice however, the player will first be transferred into that square, and then repeat the procedure again in the same direction. This means the player will glide on the ice until either colliding with an obstacle or reaching a square filled with gravel. Gliding on ice counts only as one move.

You have almost finished your level design. In the maze, there is a goal square that you wish to reach. You still have to choose a square to be the starting point of the player. Since you do not want the level to be too easy, you want to make sure the number of moves needed to get from the starting point to the goal is sufficiently high.

Can you compute the minimum number of moves needed to get from each point in the maze to the goal? Note that move may result in the player traveling multiple squares if gliding on the ice.

입력

The first line of the input contains the two integers 3≤C≤1,0003 \le C \le 1\\,000 and 3≤R≤1,0003 \le R \le 1\\,000, the number of columns and rows that the maze consists of.

The next RR lines contains CC characters each, describing the maze. Each square in the maze is represented by one of the following characters:

  • a period (.) represents a gravel square
  • a pound sign (#) represents an obstacl
  • an underscore (_) represents an ice square
  • an M (M) represents the goal in the maze, which is also covered in gravel

The edges of the maze are always surrounded by obstacle squares.

출력

Output RR lines with CC integers each, one for each square, containing the number of moves needed to reach the goal.

If it is not possible to reach the target from a square, output −1-1 instead for that square.

예제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