Responsive image

Problem 1045 --Maze Problem

1045: Maze Problem

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 0
[Submit][Status][Web Board][Creator:]

Description

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

Input

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.

Output

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

Sample Input

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

Sample Output

9

Source

 

[Submit][Status]
ACM算法攻关部
  • Anything about this OnlineJudge, Please Contact Administrator. Click add QQ

    OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap

    Copyright 2016 ACM算法攻关部
    关于网站改版