穿越雷区（2015年第六届蓝桥杯国赛JAVA语言B组第四题）

标题：穿越雷区

X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

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

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

数据格式要求：

输入第一行是一个整数n，表示方阵的大小， 4<=n<100
接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。
A，B都只出现一次。

要求输出一个整数，表示坦克从A区到B区的最少移动步数。
如果没有方案，则输出-1

例如：
用户输入：
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

则程序应该输出：
10

资源约定：
峰值内存消耗（含虚拟机） < 512M
CPU消耗  < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。

此题我使用的BFS的非递归形式，（同时将最短路径的走法也记录了下来），此题需要注意的地方是在对p2进行入队的操作时必须新创建一个point对象！！！代码如下：

package 历届试题;

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

public class 第六届JAVA国赛B组第四题 {

    static class point {

        private int x;
        private int y;
        private int step;
        private String road;

        public point() {
        }

        public point(int x, int y, int step, String road) {
            this.x = x;
            this.y = y;
            this.step = step;
            this.road = road;
        }
    }
    private static final int dir[][] = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static final String path[] = new String[]{"上", "右", "下", "左"};
    private static final char[][] c = new char[101][101];
    private static final boolean[][] vis = new boolean[101][101];

    public static void main(String[] args) {
        long start=System.currentTimeMillis();
        Scanner sc = new Scanner(System.in);
        int min = Integer.MAX_VALUE;
        String r="";
        int n = Integer.parseInt(sc.nextLine());
        int sx = 0, sy = 0, ex = 0, ey = 0;
        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < n; j++) {
                c[i][j] = s.charAt(j * 2);
                if (c[i][j] == 'A') {
                    sx = i;
                    sy = j;
                }
                if (c[i][j] == 'B') {
                    ex = i;
                    ey = j;
                }
            }
        }

        point p1 = new point();
        point p2 = new point();
        LinkedList<point> ld = new LinkedList<>();
        p1.x = sx;
        p1.y = sy;
        vis[p1.x][p1.y] = true;

        ld.offer(new point(p1.x, p1.y, 0, ""));
        while (!ld.isEmpty()) {
            p1 = ld.poll();
            if (p1.x == ex && p1.y == ey) {
                if (p1.step < min) {
                    min = p1.step;
                    r=p1.road;
                }
            }
            for (int i = 0; i < 4; i++) {
                p2.x = p1.x + dir[i][0];
                p2.y = p1.y + dir[i][1];
                if (p2.x >= 0 && p2.x < n && p2.y >= 0 && p2.y < n && c[p1.x][p1.y] != c[p2.x][p2.y] && vis[p2.x][p2.y] == false) {
                    vis[p2.x][p2.y] = true;
                    ld.offer(new point(p2.x, p2.y, p1.step + 1, p1.road + path[i]));
                }
            }
        }

        System.out.println(min);
        System.out.println(r);
        System.out.println(System.currentTimeMillis()-start);
    }

}