1 //重新写了下hdu1253,以前没剪枝的全部TLE掉了，加了几个小剪枝就过了.
2 //所以还是有点启发的
http://acm.hdu.edu.cn/showproblem.php?pid=1253
3 #include <iostream>
4 #include <queue>
5
6 using namespace std;
7 const int N=51;
8 const int M=51;
9 const int R=51;
10 int mp[N][M][R];
11 bool mark[N][M][R];
12 int A,B,C,T,Road;
13 int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
14 struct Node
15 {
16 int xi,yi,zi;
17 int time;
18 Node(int x=0,int y=0,int z=0,int t=0):xi(x),yi(y),zi(z),time(t){
19 };
20 bool operator==(const Node& c)const{
21 if(xi == c.xi && yi == c.yi && zi == c.zi)return true;
22 return false;
23 };
24 };
25 inline void Input()
26 {
27 //cin>>A>>B>>C>>T;
28 Road=0;
29 scanf("%d%d%d%d",&A,&B,&C,&T);
30 for(int i=0;i<A;i++)
31 for(int j=0;j<B;j++)
32 for(int r=0;r<C;r++){
33 scanf("%d",&mp[i][j][r]);
34 if(mp[i][j][r]==0)
35 ++Road;
36 }
37 }
38 inline int BFS()
39 {
40 queue<Node> que;
41 Node start(0,0,0),end(A-1,B-1,C-1);
42 que.push(start);
43 memset(mark,0,sizeof(mark));
44 mark[0][0][0]=true;
45 Node ans;
46 while(!que.empty()){
47 Node tmp=que.front();
48 que.pop();
49 for(int i=0;i<6;i++){
50 ans.xi=tmp.xi+dir[i][0];
51 ans.yi=tmp.yi+dir[i][1];
52 ans.zi=tmp.zi+dir[i][2];
53 ans.time=tmp.time+1;
54 if(ans==end){
55 return ans.time>T?-1:ans.time;
56 }
57 if(ans.time>=T+1)return -1;
58 if(ans.xi<0||ans.yi<0||ans.zi<0||ans.xi>=A||ans.yi>=B||ans.zi>=C)continue;
59 if(mp[ans.xi][ans.yi][ans.zi]==1)continue;
60 if(mark[ans.xi][ans.yi][ans.zi])continue;
61 que.push(ans);
62 mark[ans.xi][ans.yi][ans.zi]=true;
63 }
64 }
65 return -1;
66 }
67 int main()
68 {
69 int c;
70 scanf("%d",&c);
71 while(c--){
72 Input();
73 if(mp[A-1][B-1][C-1] == 1 || A+B+C > T || A+B+C>Road )printf("-1\n");//剪枝
74 else printf("%d\n",BFS());
75 }
76 return 0;
77 }
posted on 2008-07-21 13:31
小果子 阅读(361)
评论(0) 编辑 收藏 引用