package com.ywt11;
import java.util.Scanner;
/**
*魔王住在一個(gè)城堡里,城堡是一個(gè)A*B*C的立方體,可以被表示成A個(gè)B*C的矩陣,
* 剛開始Ignatius被關(guān)在(0,0,0)的位置,離開城堡的門在(A-1,B-1,C-1)的位置,
* 現(xiàn)在知道魔王將在T分鐘后回到城堡,Ignatius每分鐘能從一個(gè)坐標(biāo)走到相鄰的六個(gè)坐標(biāo)中的其中一個(gè).
* 現(xiàn)在給你城堡的地圖,請(qǐng)你計(jì)算出Ignatius能否在魔王回來(lái)前離開城堡(只要走到出口就算離開城堡
*,如果走到出口的時(shí)候魔王剛好回來(lái)也算逃亡成功),如果可以請(qǐng)輸出需要多少分鐘才能離開,如果不能則輸出-1
試數(shù)據(jù)的第一行是四個(gè)正整數(shù)A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它們分別代表城堡的大小和魔王回來(lái)的時(shí)間.然后是A塊輸入數(shù)據(jù)(先是第0塊,然后是第1塊,第2塊......),每塊輸入數(shù)據(jù)有B行,每行有C個(gè)正整數(shù),代表迷宮的布局,其中0代表路,1代表墻.(如果對(duì)輸入描述不清楚,可以參考SampleInput中的迷宮描述,它表示的就是上圖中的迷宮)
* @author Administrator
*
INPUT
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0
OUTPUT 11
INPUT
3 3 3 20
0 1 1
0 0 1
1 1 1
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 0 0
OUTPUT 6
*
*/
public class Num1 {
private int[][][] tagArr = null ; //迷宮
private int[][][] markArr = null ; //標(biāo)記數(shù)組
private int[][] moveArr = {//上下左右
{0 , 1},
{1 , 0 },
{0 , -1},
{-1 , 0}
};
private int [] step = {-1 , 1}; //前后
private int T = 0 ; ///魔王回來(lái)的時(shí)間
private int allTime = 0 ; // 記錄需要走出迷宮所花費(fèi)的總時(shí)間
private void process() {
Scanner sc = new Scanner(System.in);
String temp[] = sc.nextLine().split(" ");
tagArr = new int[Integer.valueOf(temp[0])][Integer.valueOf(temp[1])][Integer.valueOf(temp[2])];
T = Integer.valueOf(temp[3]);
for (int i = 0; i < tagArr.length; i++) {
for (int j = 0; j < tagArr[i].length; j++) {
temp = sc.nextLine().split(" ");
for (int k = 0; k < tagArr[i][j].length; k++) {
tagArr[i][j][k] = Integer.valueOf(temp[k]);
}
}
}
markArr = new int[tagArr.length][tagArr[0].length][tagArr[0][0].length];
searchPath(0,0,0);
}
private void searchPath(int witch ,int x , int y){
//x,y越界
//witch越界
//已經(jīng)走過(guò)
if(x < 0 || y < 0 || x >= this.tagArr[0].length || y >=this.tagArr[0][0].length || witch < 0 || witch >= this.tagArr.length|| markArr[witch][x][y] == -1){
return ;
}
//遇到墻壁
if(this.tagArr[witch][x][y] == 1){
return ;
}
allTime ++ ; //總時(shí)間加1
markArr[witch][x][y] = -1 ;
//走到出口
int len = this.tagArr.length;
if(witch == this.tagArr.length-1 && x == this.tagArr[len-1].length-1 && y == this.tagArr[len-1][0].length-1){
if(allTime >= T){
System.out.println(-1);
}else{
System.out.println(allTime-1); //這里要減一是因?yàn)榈谝徊蕉嘤?jì)算了一次
}
System.exit(0);
}
int nextX = 0 ; //下一個(gè)x坐標(biāo)
int nextY = 0 ; //下一個(gè)y坐標(biāo)
for (int i = 0; i < moveArr.length; i++) {
nextX = moveArr[i][0] + x ;
nextY = moveArr[i][1] + y ;
searchPath(witch , nextX , nextY) ;
}
int nextWitch = 0 ; //下一個(gè)二維矩陣
for (int i = 0; i < step.length; i++) {
nextWitch = step[i]+witch;
searchPath(nextWitch , x , y ) ;
}
allTime -- ;
markArr[witch][x][y] = 0 ;
}
public static void main(String[] args) {
Num1 demo = new Num1();
demo.process();
}
}
仔細(xì)分析一下就會(huì)發(fā)現(xiàn)，這其實(shí)是一個(gè)多個(gè)二維迷宮，只不過(guò)你需要從一個(gè)二維迷宮上走到另一個(gè)相鄰的二維迷宮上，為了實(shí)現(xiàn)這個(gè)，你必須定義一個(gè)step數(shù)組，保證可以在相鄰的二維數(shù)組中穿越。但是保證數(shù)組的下標(biāo)不能溢出。
