# 2015年第六屆藍橋杯JavaB組決賽題解——穿越雷區

X星的坦克戰車很奇怪，它必須交替地穿越正能量輻射區和負能量輻射區才能保持正常運轉，否則將報廢。

A – –
– – –
– –
– –
B – –

A，B都只出現一次。

5
A – –
– – –
– –
– –
B – –

10

CPU消耗  < 2000ms

``````import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int n;
public static char[][] array;
public static boolean[][] flag;
public static int xA,xB,yA,yB,countMin=-1;
public static int[][] direct={{-1,0},{1,0},{0,-1},{0,1}};
public static void DFS(int x,int y,int count,char c){
if (x==xB && y==yB){
if (countMin==-1)
countMin=count;
else
countMin=Math.min(countMin,count);
return;
}
for (int i=0;i<4;i  ){
int dx=x direct[i][0];
int dy=y direct[i][1];
if (dx>=n||dy>=n||dx<0||dy<0||flag[dx][dy])
continue;
if (c=='0'||(c==' ' && array[dx][dy]=='-')||(c=='-' && array[dx][dy]==' ')||(array[dx][dy]=='B')){
flag[dx][dy]=true;
DFS(dx,dy,count 1,array[dx][dy]);
flag[dx][dy]=false;
}
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
n=scanner.nextInt();
array=new char[n][n];
flag=new boolean[n][n];
for (int i=0;i<n;i  )
Arrays.fill(flag[i],false);
for (int i=0;i<n;i  )
for (int j=0;j<n;j  ){
array[i][j]=scanner.next().charAt(0);
char temp=array[i][j];
if (temp=='A'){
xA=i;
yA=j;
}
else if (temp=='B'){
xB=i;
yB=j;
}
}
flag[xA][yA]=true;
DFS(xA,yA,0,'0');
System.out.println(countMin);
}
}
``````