1101. 献给阿尔吉侬的花束

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

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

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

迷宫用一个 $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!

思路：

一般求最短路或最少步数的问题，基本都是用BFS。
因为BFS会按层来所搜，第一步会把所有距离为1的点搜出来，第二步则会把所有距离为2的点搜出来，以此类推。当首次遇到终点时，便是走了最少的步数到达的终点。

可见BFS天然就具有求最少步数的优势。

BFS算法属于常规算法，不过多解释了。

Java代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.io.BufferedInputStream;

public class Main {
    private static int res;
    private static int row;
    private  static int col;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(new BufferedInputStream( System.in));
        int T = scanner.nextInt();
        //共有T组数据
        while(T-- != 0){
             row = scanner.nextInt();
             col = scanner.nextInt();
            char[][] chs = new char[row][col];//存数据
            boolean[][] isVisited = new boolean[row][col];//标记当前点是否被访问过
            int[][] dist = new int[row][col];//起点到当前位置要走多少步
            int[] start = new int[2];
            //读取一组数据
            for(int i = 0;i < row;i++){
                 chs[i] = scanner.next().toCharArray();
                for(int j = 0;j < col;j++){
                    if( chs[i][j] == 'S'){//找到起点
                        start[0] = i;
                        start[1] = j;
                    }
                }
            }
            res = bfs(start,chs,isVisited,dist);
            if(res == -1){
                System.out.println("oop!");
            }else{
                System.out.println(res);
            }
        }
    }

    private static int bfs(int[] start,char[][] chs,boolean[][] isVisited,int[][] dist) {
        Queue<int[]> queue = new LinkedList<>();
        int[] dx = {0,0,-1,1};//上下左右四个方向偏移量技巧
        int[] dy = {-1,1,0,0};
        queue.add(start);
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            for(int i = 0;i < 4;i++){
                int x = point[0] + dx[i];
                int y = point[1] + dy[i];
                //当前点未越界且不是障碍物且没有被访问过
                if(x >= 0 && x < row && y >= 0 && y < col && chs[x][y] != '#' && !isVisited[x][y]){
                    isVisited[x][y] = true;
                    dist[x][y] = dist[point[0]][point[1]] + 1;
                    if(chs[x][y] == 'E'){
                        return dist[x][y];
                    }
                    queue.add(new int[]{x,y});
                }
            }
        }
        return -1;//如果上面没有返回，则说明没有找到终点，我们以-1表示没有找到终点
    }
}

这里需要扩展的点是如下读取数据的一段简单的代码：

//读取一组数据
            for(int i = 0;i < row;i++){
                 chs[i] = scanner.next().toCharArray();
                for(int j = 0;j < col;j++){
                    if( chs[i][j] == 'S'){//找到起点
                        start[0] = i;
                        start[1] = j;
                    }
                }

可以看到其中一行chs[i] = scanner.next().toCharArray();，发现可以直接将一个一维数组赋值给二维数组的一行（chs是二维数组）。

另外需要注意的是这里只能用next(),而不能是nextLine()。

首先，next()一定要读取到有效字符后才可以结束输入，对输入有效字符之前遇到的空格键、Tab键或Enter键等结束符，next()方法会自动将其去掉，只有在输入有效字符之后，next()方法才将其后输入的空格键、Tab键或Enter键等视为分隔符或结束符。简单地说，next()查找并返回来自此扫描器的下一个完整标记。完整标记的前后是与分隔模式匹配的输入信息，所以next()方法不能得到带空格的字符串；而nextLine()方法的结束符只是Enter键，即nextLine()方法返回的是Enter键之前的所有字符，它是可以得到带空格的字符串的。

鉴于以上两种方法的只要区别，我们一定要注意next()方法和nextLine()方法的连用，下面举个例子来说明：

import java.util.Scanner;

public class Test_next {
    public static void main(String[] args) {
        String s1,s2;
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入第一个字符串："); 
        s1=scanner.next();
        System.out.println("请输入第二个字符串：");
        s2=scanner.nextLine();
        System.out.println("输入的字符串是："+s1+s2);
    }
}

测试结果

请输入第一个字符串：
home
请输入第二个字符串：
输入的字符串是：home

结论
nextLine()自动读取了被next()去掉的Enter作为他的结束符，所以没办法给s2从键盘输入值。

经过验证，其他的next的方法，如nextDouble() ，nextFloat() ， nextInt() 等与nextLine()连用时都存在这个问题。

解决的办法
在每一个 next()、nextDouble() 、nextFloat()、nextInt() 等语句之后加一个nextLine()语句，将被next()去掉的Enter结束符过滤掉,但为了避免出错，写题时尽量不要同时使用next()和nextLine()方法。

import java.util.Scanner;

public class Test_next {
    public static void main(String[] args) {
         String s1,s2;
         Scanner scanner=new Scanner(System.in);
         System.out.println("请输入第一个字符串："); 
         s1=scanner.next();
         scanner.nextLine();
         System.out.println("请输入第二个字符串：");
         s2=scanner.nextLine();
         System.out.println("输入的字符串是："+s1+s2);
     }

 }

测试结果

请输入第一个字符串：
home
请输入第二个字符串：
work
输入的字符串是：homework