Leecode learning notes - the shortest path for a robot to reach its destination

link ：https://www.nowcoder.com/questionTerminal/a4d87cae999244acbdd57bb0385a1d0b
source ： Cattle from

Small C Recently, I am studying robots , He wanted to see if his robot was smart enough , So he put the robot in a n*m In the maze of , See if the robot can reach its destination in the shortest time , But small C I don't know the shortest time , Now please help him calculate the shortest time for the robot to reach its destination ？

Enter two integers in the first row of data n and m.n and m The scope of the [10,500]. Next n That's ok , Each row m Elements , Each square of the maze . 'S’ Represents the starting point of the robot ,
'T’ Means the destination , '#' Indicates that the square cannot pass , '.' Means that it can be passed .

An integer is output to indicate the shortest time for the robot to reach the destination , If the robot can't reach its destination , Output -1.

Input

3 3
S…
##.
.T.

Output

5

First of all, this question uses dfs Overtime
Why do I need to use bfs？bfs Be similar to “ Ripple of water ” Spread out , That is, the first point that meets the conditions is the nearest point . The difficulty here is to record the distance from each point to the starting point , That is, in addition to the location information in the queue , Also put distance information , Every point should have , Why? ？ Here's the picture , In fact, both sides can walk , But the left side comes first and returns , Therefore, in addition to recording the information of each point, the distance information should also be recorded

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});
            }
        }
    }
}