【思路】
迷宫最短路问题。BFS。
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
class node{
int t, x, y;
public node(int tt, int xx, int yy){
t = tt;
x = xx;
y = yy;
}
}
public class Main{
//上右下左
static int dx []= {-1, 0, 1, 0};
static int dy []= {0, 1, 0, -1};
public static int bfs(char [][] f, int x, int y, int n, int m){
Queue<node> q = new LinkedList<node>();
boolean vis[][] = new boolean[n][m];
q.add(new node(0, x, y));
vis[x][y] = true;
while(! q.isEmpty()) {
node head = q.poll();
int sx = head.x, sy = head.y, st = head.t;
if( f[sx][sy] == 'E') return st;
for(int i = 0; i < 4; i++) {
int nx = sx + dx[i], ny = sy + dy[i];
if(nx < 0|| nx >= n || ny < 0 || ny >= m || f[nx][ny] == '#' || vis[nx][ny])
continue;
vis[nx][ny] = true;
q.add(new node( st + 1, nx, ny));
}
}
return 0;
}
public static void main(String args[]) throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(bf.readLine());
while(T-- > 0){
String s[] = bf.readLine().split(" ");
int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
char [][] f= new char[n][m];
for(int i = 0; i < n; i++) f[i] = bf.readLine().toCharArray();
int sx = 0, sy = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(f[i][j] == 'S'){
sx = i;
sy = j;
}
int ans = bfs(f, sx, sy, n, m) ;
if( ans == 0)
log.write("oop!\n");
else
log.write(ans+"\n");
}
log.flush();
log.close();
bf.close();
}
}