牛客-走出迷宫_题目描述 迷宫的游戏,相信大家都听过,现在我们用一个n*m的矩阵表示一个迷宫,例如:

题目链接

小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个N*M的矩阵。
小明的起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。
障碍物不能通过。小明如果现在在点（x，y）处，那么下一步只能走到相邻的四个格子中的某一个：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；
小明想要知道，现在他能否从起点走到终点。
输入描述:
本题包含多组数据。
每组数据先输入两个数字N,M
接下来N行，每行M个字符，表示地图的状态。
数据范围：
2<=N,M<=500
保证有一个起点S，同时保证有一个终点E.
输出描述:
每组数据输出一行，如果小明能够从起点走到终点，那么输出Yes，否则输出No

bfs吧

import java.util.ArrayList;
import java.util.Scanner;
 import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
public class Main {
    static int endx;
    static int endy;
    static int a[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
 
    static class point {
        int x, y;
 
        public point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            scanner.nextLine();
            int sx = 0;
            int sy = 0;
            char c[][] = new char[n][m];
            for (int i = 0; i < n; i++) {
                String s1 = scanner.nextLine();
                for (int j = 0; j < m; j++) {
                    c[i][j] = s1.charAt(j);
                    if (c[i][j] == 'S') {
                        sx = i;
                        sy = j;
                    }
                    if (c[i][j] == 'E') {
                        endx = i;
                        endy = j;
                    }
                }
            }
            int t = bfs(c, sx, sy);
            if (t == 1)
                System.out.println("Yes");
            else {
                System.out.println("No");
            }
        }
    }
 
    public static boolean check(char[][] matrix, point a) {
        int n = matrix.length - 1, m = matrix[0].length - 1;
        if (a.x < 0 || a.x > n || a.y < 0 || a.y > m || matrix[a.x][a.y] == '#')
            return false;
        return true;
    }
 
    private static int bfs(char[][] c, int sx, int sy) {
        ArrayList<point> list = new ArrayList<>();
        list.add(new point(sx, sy));
        while (list.size() != 0) {
            point b = list.get(0);
            list.remove(0);// 删除该点
            if (b.x == endx && b.y == endy) {
                return 1;
            }
            for (int i = 0; i < 4; i++) {
                int x = b.x + a[i][0];
                int y = b.y + a[i][1];
                point p = new point(x, y);
                if (check(c, p)) {
                    list.add(p);
                    c[x][y] = '#';
                }
            }
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83