Maze Problems

<p> Given a maze, find a shortest path from start to goal. </p>

<p> Input consists serveral test cases. </p> <p> First line of the input contains number of test case T. </p> <p> For each test case the first line contains two integers N , M ( 1 &lt;= N, M &lt;= 100 ). </p> <p> Each of the following N lines contain M characters. Each character means a cell of the map. </p> <p> Here is the definition for chracter. </p> <p> &nbsp; </p> <p> Constraint: </p> <ul> <li> For a character in the map: <ul> <li> 'S' : start cell </li> <li> 'E' : goal cell </li> <li> '-' : empty cell </li> <li> '#' : obstacle cell </li> </ul> </li> <li> no two start cell exists. </li> <li> no two goal cell exists. </li> </ul>

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