2018JavaB组省赛

穿越雷区

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

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

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

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

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

资源约定: 峰值内存消耗 < 512M CPU消耗 < 1000ms

import java.util.Scanner;

public class Minefields {
    static int [][] direction={{1,0},{0,1},{-1,0},{0,-1}};
    static String[][] maze;
    static boolean[][] vis;
    static int [][] dis;
    static int[] start;
    static int[] end;
    public static void main(String [] args){
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();
        maze=new String[m][m];
        vis=new boolean[m][m];
        dis=new int[m][m];
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                dis[i][j]=0;
                maze[i][j]=input.next();
                if(maze[i][j].equals("A")){
                    start=new int[]{i,j,0};
                }else if(maze[i][j].equals("B")){
                    end=new int[]{i,j};
                }
            }
        }
        bfs();
        for (int[] s:dis) {
            System.out.println(Arrays.toString(s));
        }
    }
    public static void bfs(){
        LinkedList<int[]> queue=new LinkedList<>();
        queue.add(start);
        vis[start[0]][start[1]]=true;
        dis[start[0]][start[1]]=0;
        while(!queue.isEmpty()){
            int [] node=queue.pollFirst();

            if (node[0]==end[0]&&node[1]==end[1]){
                System.out.println(node[2]);
                break;
            }
            int x=node[0];
            int y=node[1];
            String flag=maze[x][y];
            System.out.print(flag);
            for (int[] dir:direction) {
                int newx=x+dir[0];
                int newy=y+dir[1];
                if (check(newx,newy,flag)&&!vis[newx][newy]){
                    queue.addLast(new int[]{newx,newy,node[2]+1});
                    vis[newx][newy]=true;
                }
            }
        }
    }
    public static boolean check(int x, int y,String flag){
        if (x<0||x>=maze.length||y<0||y>=maze.length||maze[x][y].equals(flag)) {
            return false;
        }
        return true;
    }
}