Bomb

면접 대비

시간 제한1초메모리 제한1024 MB

요약

파괴 가능한 벽이 있는 3차원 미로에서 시작점에서 출구까지 가는 데 부숴야 하는 벽의 최소 개수를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, BFS, 최단 경로, 행렬
정답자: 아직 제출이 없습니다

문제

You decide to create a game involving a 3D maze with destructible walls, where all the character has to work with is bombs. In order to determine the number of bombs to provide for each level, you need to know the minimum amount necessary to reach the exit and base it off of that. Your task is to write a program that will find the smallest number of bombs necessary to reach the exit. Each bomb can destroy one wall, leaving a blank space in its place.

입력

The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will start with three integers f, r, and c, representing the number of layers, rows, and columns, respectively. The next f sets of r lines will be the maze, with every set of r lines being one layer of the maze.

The # represents a destructible wall, . represents an open space, S is the start location, and E is the exit location. You can only move up, down, left, and right (i.e., you cannot move diagonally). You can move freely between layers, but a move between layers stays in the same relative grid location.

출력

Output the smallest number of bombs necessary to escape the maze. There will be no trailing white space.

예제1

예제 1

입력

2
2 3 3
S##
##E
###
#.#
#..
###
1 2 10
S#.####.#E
..##..###.

예상 출력

1
5