阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。

今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。

现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。

迷宫用一个 R×C 的字符矩阵来表示。

字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。

阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。

输入格式

第一行是一个正整数 T，表示一共有 T组数据。

每一组数据的第一行包含了两个用空格分开的正整数 R� 和 C�，表示地图是一个 R×C的矩阵。

接下来的 R 行描述了地图的具体内容，每一行包含了 C个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。

输出格式

对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。

若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。

每组数据的输出结果占一行。

数据范围

1 < T ≤10,\ 2 ≤ R, C ≤ 200

输入样例：

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

输出样例

5
1
oop!

代码详解

import java.util.*;
import java.io.*;
public class Main {

    static int N = 210;
    static int r, c;
    static char[][] g = new char[N][N]; // 用来接受地图
    static int[][] dist = new int[N][N]; // 存起点到每一个点的路径长度，同时可以当做判重数组
    static int[][] se = new int[3][3];  //保存开头可结束坐标
    static BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in)); 


    public static void main(String[] args) throws IOException{

        int T = Integer.parseInt(bReader.readLine().trim());
        while(T-- > 0) {
            String s[] = bReader.readLine().split(" ");  // 读入行列
            r = Integer.parseInt(s[0]);  // r 行
            c = Integer.parseInt(s[1]);  // 每行 c 个字符
            for(int i = 0; i < r; i++) {
                g[i] = bReader.readLine().toCharArray(); // 每读入一行， 将字符串转化为字符数组
            }
            for(int i = 0; i < r; i++) {
                // 保存开始和结束点的坐标
                for(int j = 0; j < c; j++) {
                    if(g[i][j] == 'S') {
                        se[0][0] = i;
                        se[0][1] = j;
                    }
                    if(g[i][j] == 'E') {
                        se[1][0] = i;
                        se[1][1] = j;
                    }
                }
            }
            int res = dfs(se);
            if(res == -1)System.out.println("oop!");
            else {
                System.out.println(res);
            }
        }

    }


    // 传入迷宫的起始和结束坐标
    public static  int dfs(int[][] se2) {
        // TODO Auto-generated method stub

        LinkedList<PII> queue = new LinkedList<>(); // 建立一个PII类型的队列
        for(int i = 0; i < r; i++)Arrays.fill(dist[i], -1); // 先将dist所以初试化为-1
        dist[se2[0][0]][se2[0][1]] = 0;  // 起始点的坐标标记为 0

        queue.offer(new PII(se2[0][0], se2[0][1]));
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};//四个方向
        while(!queue.isEmpty()) {
            PII tPii = queue.poll(); // 取出一个元素，然后遍历元素相邻的结点

            for(int i = 0; i < dx.length; i++) {
                int x = tPii.x + dx[i];
                int y = tPii.y + dy[i];  // 坐标走到对应的地方

                if(x < 0 || y < 0 || x >= r || y >= c)continue; // 坐标点位置出界
                if(g[x][y] == '#')continue; // 遇到障碍物
                if(dist[x][y] != -1)continue;  // 之前遍历过

                dist[x][y] = dist[tPii.x][tPii.y] + 1; // 将现在坐标的距离 + 1

                if(g[x][y] == 'E')return dist[x][y];  // 找到当前坐标 返回距离；
                queue.offer(new PII(x, y));
            }

        }

        return -1;
    }

}
class PII{
    int x;
    int y; 
    public  PII(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

注意点

BFS能找到最少步数，也就是最短路径

因为BFS是按层来遍历的，会先把所有距离为0的点遍历完，然后再遍历所有距离为1的点，按这样的顺序来遍历的，再遍历所有距离为2的点，一层一层往外扩展，因此第一次扩展到终点时，必然是最短距离