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

NO IMAGE

標題:穿越雷區

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,否則按無效程式碼處理。

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);
}
}