题目描述

X 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。

某坦克需要从 A 区到 B 区去（A,B 区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

已知的地图是一个方阵，上面用字母标出了 A,B 区，其它区都标了正号或负号分别表示正负能量辐射区。

例如：

A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
坦克车只能水平或垂直方向上移动到相邻的区。

输入格式
第一行是一个整数 n，表示方阵的大小。

接下来是 n 行，每行有 n 个数据，可能是 A，B，+，- 中的某一个，中间用空格分开。A，B 都只出现一次。

输出格式
一个整数，表示坦克从 A 区到 B 区的最少移动步数。

如果没有方案，则输出 −1。

数据范围
4≤n<100
输入样例：

样例

5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

输出样例：
10

算法(bfs)

Java 代码

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

public class Main{
    static int n;
    static boolean[][] sr;
    static String[][] s;
    static int ax,ay,bx,by;//b点的坐标
    static int min = 10000;//因为n的最大值为100，那么图上只有10000个点。所以10000是步数的最大值了，因为不支持往回走
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = Integer.parseInt(in.nextLine());//这样子写可以把数字后面的回车给消耗掉，不然会被下面读进去
        s = new String[n][];
        sr = new boolean[n][n];
        for(int i = 0;i < n;i++){
            s[i] = in.nextLine().split(" ");
            for(int j = 0;j < s[i].length;j++) {//找出起点和终点
                if(s[i][j].equals("A")) {
                    ax = i;
                    ay = j;
                }
                if(s[i][j].equals("B")) {
                    bx = i;
                    by = j;
                }
            }
        }
        in.close();
        bfs();
        if(min == 10000) System.out.println(-1);
        else System.out.println(min);
    }
    public static void bfs() {
        int[] a = new int[]{0,-1,0,1};
        int[] b = new int[]{-1,0,1,0};//用于物体的上下左右移动
        LinkedList<Edge> q = new LinkedList<>();//集合
        q.add(new Edge(ax,ay,0));
        sr[ax][ay] = true;
        while (!q.isEmpty()) {
            Edge e = q.poll();
            for(int j = 0;j < a.length;j++) {
                int x = e.x + a[j];
                int y = e.y + b[j];
                if(x >= n || x < 0 || y >= n || y < 0) continue;//这样指走出了边界
                if(s[e.x][e.y].equals(s[x][y]) || sr[x][y]) continue;//两个电荷相同，那么就不能走
                if (x == bx && y == by) min = Math.min(min,e.count + 1);//步数要加上一，因为在前面没有加过一
                q.add(new Edge(x,y,e.count + 1));
                sr[x][y] = true;//这个是在记录那些点走过了吗
            }
        }
    }
}
class Edge{
    int x;//横坐标
    int y;//纵坐标
    int count;//步数

    public Edge(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}