hdu

http://acm.hdu.edu.cn/showproblem.php?pid=1240

开始没仔细看题，看懂了发现就是一个裸的bfs,注意坐标是三维的,然后每次可以扩展出6个方向。

第一维代表在第几层。后两维代表行和列。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 struct point
 6 {
 7     int x,y,z,step;
 8     bool operator < (const point a) const
 9     {
10         return step>a.step;
11     }
12 };
13 point t,e;
14 int n;
15 char maze[15][15][15];
16 int used[15][15][15];
17 int dir[6][3]={{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}};
18 
19 void bfs()
20 {
21     memset(used,0,sizeof(used));
22     priority_queue<point>que;
23     que.push(t);
24     used[t.z][t.x][t.y]=1;
25     while(!que.empty())
26     {
27         point s=que.top(); que.pop();
28       //  printf("%d %d %d %d
",s.z,s.x,s.y,s.step);
29         if(s.x==e.x&&s.y==e.y&&s.z==e.z) {printf("%d %d
",n,s.step);return;}
30         for(int i=0;i<6;i++)
31         {
32             t.x=s.x+dir[i][0],t.y=s.y+dir[i][1],t.z=s.z+dir[i][2];
33             if(t.x>=0&&t.x<n&&t.y>=0&&t.y<n&&t.z>=0&&t.z<n&&maze[t.z][t.x][t.y]!='X'&&!used[t.z][t.x][t.y])
34             {
35                 t.step=s.step+1;
36                 used[t.z][t.x][t.y]=1;
37                 que.push(t);
38             }
39         }
40     }
41     printf("NO ROUTE
");
42 }
43 int main()
44 {
45    // freopen("a.txt","r",stdin);
46     char s[10];
47     while(~scanf("%s",s))
48     {
49         scanf("%d",&n);
50         for(int i=0;i<n;i++)
51             for(int j=0;j<n;j++)
52             scanf("%s",maze[i][j]);
53         scanf("%d%d%d",&t.y,&t.x,&t.z);
54         t.step=0;
55         scanf("%d%d%d",&e.y,&e.x,&e.z);
56         scanf("%s",s);
57         bfs();
58     }
59     return 0;
60 }

http://acm.hdu.edu.cn/showproblem.php?pid=1253

这题用优先队列是超时的,普通队列可以过。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 struct point
 6 {
 7     int x,y,z,time;
 8 }s,e;
 9 int maze[55][55][55];
10 int dir[6][3]= {{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}};
11 
12 int main()
13 {
14     //freopen("a.txt","r",stdin);
15     int d,flag;
16     int a,b,c,t;
17     queue<point>que;
18     scanf("%d",&d);
19     while(d--)
20     {
21         scanf("%d%d%d%d",&a,&b,&c,&t);
22         for(int i=0; i<a; i++)
23             for(int j=0; j<b; j++)
24                 for(int k=0; k<c; k++)
25                 scanf("%d",&maze[i][j][k]);
26         while(!que.empty()) que.pop();
27         s.x=0,s.y=0,s.z=0,s.time=0;
28         flag=0;
29         que.push(s);
30         maze[s.z][s.x][s.y]=1;
31         while(!que.empty())
32         {
33             e=que.front();
34             que.pop();
35             //printf("%d %d %d %d
",e.z,e.x,e.y,e.time);
36             if(e.z==a-1&&e.x==b-1&&e.y==c-1&&e.time<=t)
37             {
38                 printf("%d
",e.time);
39                 flag=1;
40                 break;
41             }
42             for(int i=0; i<6; i++)
43             {
44                 s.x=e.x+dir[i][0];
45                 s.y=e.y+dir[i][1];
46                 s.z=e.z+dir[i][2];
47                 if(s.z>=0&&s.z<a&&s.x>=0&&s.x<b&&s.y>=0&&s.y<c&&maze[s.z][s.x][s.y]!=1)
48                 {
49                     s.time=e.time+1;
50                     if(s.time<=t)
51                     {
52                         maze[s.z][s.x][s.y]=1;
53                         que.push(s);
54                     }
55                 }
56             }
57         }
58         if(!flag) printf("-1
");
59     }
60     return 0;
61 }