HDU1253 勝利大逃亡 （三維bfs）

Input輸入資料的第一行是一個正整數K,表明測驗資料的數量.每組測驗資料的第一行是四個正整數A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它們分別代表城堡的大小和魔投訓來的時間.然后是A塊輸入資料(先是第0塊,然后是第1塊,第2塊......),每塊輸入資料有B行,每行有C個正整數,代表迷宮的布局,其中0代表路,1代表墻.(如果對輸入描述不清楚,可以參考Sample Input中的迷宮描述,它表示的就是上圖中的迷宮) 

特別注意:本題的測驗資料非常大,請使用scanf輸入,我不能保證使用cin能不超時.在本OJ上請使用Visual C++提交. 
Output對于每組測驗資料,如果Ignatius能夠在魔投訓來前離開城堡,那么請輸出他最少需要多少分鐘,否則輸出-1. 
Sample Input

1
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

Sample Output

11

對java不友好啊，加個快速輸入輸出

代碼：

import java.util.*;
import java.util.Comparator;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
 class Node{
         int x;
         int y;
         int z;
         int step;
         public Node(int x,int y,int z,int step){
                 this.x=x; this.y=y; this.z=z;
                 this.step=step;
         }
 }
public class Main{
    static class FastScanner{//快速輸入
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(InputStream in) {
          br = new BufferedReader(new InputStreamReader(in),16384);
          eat("");
        }
        public void eat(String s) {
          st = new StringTokenizer(s);
        }
        public String nextLine() {
          try {
              return br.readLine();
          } catch (IOException e) {
              return null;
          }
        }
        public boolean hasNext() {
          while(!st.hasMoreTokens()) {
              String s = nextLine();
              if(s==null) return false;
              eat(s);
          }
          return true;
        }
        public String next() {
          hasNext();
          return st.nextToken();
        }
        public int nextInt() {
          return Integer.parseInt(next());
        }
    }
    static FastScanner scan = new FastScanner(System.in);//輸入
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//輸出
        static final int N=55;
        static  int map[][][]=new int[N][N][N];
        static int a,b,c,T;
        static boolean vis[][][]=new boolean[N][N][N];
        static ArrayDeque<Node> q=new ArrayDeque<Node>();
        static int dx[]={1,-1,0,0,0,0};
        static int dy[]={0,0,1,-1,0,0};
        static int dz[]={0,0,0,0,1,-1};
        static int bfs(){
                while(!q.isEmpty()) q.poll();
                vis[0][0][0]=true;
                q.offer(new Node(0,0,0,0));
                while(!q.isEmpty()){
                        Node s=q.poll();
                        if(s.x==a-1 && s.y==b-1 &&s.z==c-1 &&s.step>T)   return -1;
                        if(s.x==a-1 && s.y==b-1 &&s.z==c-1 &&s.step<=T) return s.step;
                        for(int i=0;i<6;i++){
                                int xx=s.x+dx[i];
                                int yy=s.y+dy[i];
                                int zz=s.z+dz[i];
                                if(xx<0||yy<0||zz<0||xx>=a||yy>=b||zz>=c) continue;
                                if(vis[xx][yy][zz]||map[xx][yy][zz]==1) continue;
                                vis[xx][yy][zz]=true;
                                q.offer(new Node(xx,yy,zz,s.step+1));
                        }
                }
                return -1;
        }
        public static void main(String[] args) {
//                Scanner scan=new Scanner(System.in);
                int t=scan.nextInt();
                while(t-->0){
                        a=scan.nextInt();
                        b=scan.nextInt();
                        c=scan.nextInt();
                        T=scan.nextInt();
                        for(int i=0;i<a;i++)
                            for(int j=0;j<b;j++)
                                for(int k=0;k<c;k++){
                                      map[i][j][k]=scan.nextInt();
                                      vis[i][j][k]=false;
                                }
                        out.println(bfs());
                }
                out.flush();
        }
}

標籤：其他

上一篇：HDU2612 Find a way （雙廣搜）

下一篇：Raid5 如何不重裝系統升級硬碟