문제1052--Maze Problem

1052: Maze Problem

실행시간 제한: 2 Sec  메모리사용 제한: 128 MB
제출: 585  통과: 159
[제출] [채점기록] [묻고답하기]

문제 설명

Given a maze, find a shortest path from start to goal.

입력 설명

Input consists serveral test cases.

First line of the input contains number of test case T.

For each test case the first line contains two integers N , M ( 1 <= N, M <= 100 ).

Each of the following N lines contain M characters. Each character means a cell of the map.

Here is the definition for chracter.

 

Constraint:

  • For a character in the map:
    • 'S' : start cell
    • 'E' : goal cell
    • '-' : empty cell
    • '#' : obstacle cell
  • no two start cell exists.
  • no two goal cell exists.

출력 설명

For each test case print one line containing shortest path. If there exists no path from start to goal, print -1.

입력 예시 Copy

1
5 5
S-###
-----
##---
E#---
---##

출력 예시 Copy

9

출처/분류