穿越雷区（Java--BFS解法）

穿越雷区（Java–BFS解法）

题目链接：http://oj.ecustacm.cn/problem.php?id=1266
解题代码（内含注释思路）

import java.util.*;

public class Main {
    static int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
    static String[][] map = new String[100][100];
    static int[][] vis = new int[100][100];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) 
                map[i][j] = sc.next();
        int ax=0,ay=0,bx=0,by=0;
        for(int i=0;i<n;i++)//计算起点坐标、终点坐标
            for(int j=0;j<n;j++) {
                ax = (map[i][j].equals("A") ? i:ax); ay = (map[i][j].equals("A") ? j:ay);
                bx = (map[i][j].equals("B") ? i:bx); by = (map[i][j].equals("B") ? j:by);
            }
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(ax,ay,0,"0"));
        while(!queue.isEmpty()){
            Node node = queue.poll();
            //出界考虑，跳过
            if (node.x<0||node.x>=n||node.y<0||node.y>=n) continue;
            //违规走法被拒绝，跳过【不能连续++，不能连续--】
            if (node.last.equals(map[node.x][node.y])) continue;
            //访问过的节点，跳过，保证只输出一条路的结果
            //并且绝对是最短的
            if (vis[node.x][node.y] >= 1) continue;

            vis[node.x][node.y]++;//访问过就记录上，访问次数
            if (node.x==bx&&node.y==by)//到达了终点
                System.out.println(node.footNum);
            //四向扩散查终点
            for (int i = 0; i < 4; i++)
                queue.add(new Node(
                node.x+dir[i][0],
                node.y+dir[i][1],
                node.footNum+1,
                map[node.x][node.y]));
        }
    }

}

class Node{
    int x,y;
    int footNum;
    String last;
    public Node(int x,int y,int footNum,String last) {
        this.x=x;
        this.y=y;
        this.footNum =footNum;
        this.last=last;
    }
}
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