### 题目描述

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.

1
5 5
S-###
—–
##—
E#—
—##

9

### 代码如下

``````import java.util.*;
public class Main {
static int[][] map=new int[101][101];
static int[][] vis=new int[101][101];
static int[][] dis=new int[101][101];
static int[] qu=new int[10001];
static int[] dx= {-1,0,1,0};
static int[] dy= {0,1,0,-1};
static int x1,y1,x2,y2;
static int m,n;
public static int bfs(int x,int y) {
int u,nx,ny;
int front=0,rear=0;
u=x*m+y;
vis[x][y]=1;
dis[x][y]=0;
qu[rear++]=u;
while(front<rear) {
u=qu[front++];
x=u/m;
y=u%m;
for(int i=0;i<4;i++) {
nx=x+dx[i];ny=y+dy[i];
if(nx>=0&&nx<m&&ny>=0&&ny<n&&vis[nx][ny]==0&&map[nx][ny]==1) {
int v=0;
v=nx*m+ny;
qu[rear++]=v;
vis[nx][ny]=1;
dis[nx][ny]=dis[x][y]+1;
if(nx==x2&&ny==y2)
return dis[nx][ny];
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int t=in.nextInt();
while(t>0) {
String s="";
char[][] c=new char[101][101];
m=in.nextInt();n=in.nextInt();
s=in.nextLine();
for(int i=0;i<m;i++)
for(int j=0;j<n;j++) {
map[i][j]=0;
vis[i][j]=0;
dis[i][j]=0;
}
for(int i=0;i<m;i++) {
s=in.nextLine();
for(int j=0;j<n;j++) {
c[i][j]=s.charAt(j);
switch(c[i][j]) {
case 'S':map[i][j]=1;x1=i;y1=j;break;
case 'E':map[i][j]=1;x2=i;y2=j;break;
case '-':map[i][j]=1;break;
case '#':map[i][j]=0;break;
}
}
}
System.out.println(bfs(x1,y1));
t--;
}
}
}
``````