leecode学习笔记-机器人走到终点的最短路径

链接：https://www.nowcoder.com/questionTerminal/a4d87cae999244acbdd57bb0385a1d0b
来源：牛客网

小C最近在研究机器人，他想看看自己的机器人够不够智能，于是他将机器人放在一个n*m的迷宫中，看看机器人能不能在最短的时间内到达目的地，可是小C不知道最短的时间是多少，现在请你帮他算算机器人到达目的地的最短时间是多少？

输入数据第一行两个整数n和m。n和m的范围[10,500]。 接下来n行，每行m个元素，表示迷宫的每个方格。 'S’表示机器人的出发点,
'T’表示目的地， '#'表示该方格不能通过， '.'表示可以通过。

输出一个整数表示机器人到达目的地的最短时间，如果机器人不能到达目的地，输出-1。

输入

3 3
S…
##.
.T.

输出

5

首先这个题用dfs超时
为什么需要用bfs？bfs类似于“水的波纹”向外扩散，那就是最先找到符合条件的点就是最近的点。这里的难点就是要记录每个点距离出发的距离，即队列中除了放位置信息外，还要放距离信息，每个点都要有，为什么呢？如下图，左右其实都会走，但是左侧先到就会返回了，所以除了记录每个点位信息还要记录距离信息

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

public class Main{
    
    public static int path = 0;
    public static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
    
// int m = 3,n = 3;


        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        char[][] input = new char[m][n];
        sc.nextLine();

        for (int i = 0; i < m; i++) {
    
            String s = sc.nextLine();
            for (int j = 0; j < n; j++) {
    
                input[i][j] = s.charAt(j);
            }
        }

// for (int i = 0; i < m; i++) {
    
// for (int j = 0; j < n; j ++) {
    
// System.out.print(input[i][j] + " ");
// }
// System.out.println();
// }

        boolean[][] visited = new boolean[input.length][input[0].length];

        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (input[i][j] == 'S') {
    
// visited[i][j] =true;
                    bfs(input, i, j, visited);
                    break;
                }
            }
        }
        if (min == Integer.MAX_VALUE) {
    
            System.out.println(-1);
        } else {
    
            System.out.println(min);
        }

    }

// public static void dfs(char[][] input, int i, int j) {
    
// if (i < 0 || i >= input.length || j < 0 || j >= input[0].length ||
// input[i][j] == '#') {
    
// return;
// }
//
// if (input[i][j] == 'T') {
    
// min = Math.min(min, path);
// return;
// }
// path++;
// input[i][j] = '#';
// dfs(input, i + 1, j);
// dfs(input, i - 1, j);
// dfs(input, i, j + 1);
// dfs(input, i, j - 1);
// input[i][j] = '.';
// path--;
// }

    public static void bfs(char[][] input, int i, int j, boolean[][] visited) {
    

        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{
    i, j, 0});
        while (!que.isEmpty()) {
    
            int[] temp = que.poll();
            i = temp[0];
            j = temp[1];
            if (i >= 0 && i < input.length && j >=0 && j < input[0].length && input[i][j] != '#' && visited[i][j] == false ) {
    

                if (input[i][j] == 'T') {
    
// for (int k = 0; k < visited.length; k ++) {
    
// for (int h = 0 ; h < visited[0].length; h++) {
    
// System.out.print(visited[k][h] + " ");
// }
// System.out.println();
// }
                    min = temp[2];
                    return;
                }
                visited[i][j] = true;
                que.offer(new int[]{
    i,j + 1, temp[2] + 1});
                que.offer(new int[]{
    i,j - 1, temp[2] + 1});
                que.offer(new int[]{
    i + 1,j, temp[2] + 1});
                que.offer(new int[]{
    i - 1,j, temp[2] + 1});
            }
        }
    }
}