HDu 1240(3 Dbfs)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1240
考え方:簡単なbfsですが、私は長い間やっていました.trickがずっと気づかなかったので、2組目のデータはずっと过ごせませんでした.の


View Code

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<queue>

 5 #include<cmath>

 6 using namespace std;

 7 #define MAXN  17

 8 char map[MAXN][MAXN][MAXN];

 9 bool visited[MAXN][MAXN][MAXN];

10 int n,sx,sy,sz,ex,ey,ez,ans;

11 char str[11];

12 //up,down,forward,back,left,right;

13 int dir[6][3]={{0,0,1},{0,0,-1},{1,0,0},{-1,0,0},{0,-1,0},{0,1,0}};

14 

15 struct Node{

16     int x,y,z;

17     int step;

18 };

19 

20 bool bfs(){

21     memset(visited,false,sizeof(visited));

22     Node p,q;

23     p.x=sx,p.y=sy,p.z=sz,p.step=0;

24     visited[p.x][p.y][p.z]=true;

25     queue<Node>Q;

26     Q.push(p);

27     while(!Q.empty()){

28         p=Q.front();

29         Q.pop();

30         if(p.x==ex&&p.y==ey&&p.z==ez){

31             ans=p.step;

32             return true;

33         }

34         for(int i=0;i<6;i++){

35             q.x=p.x+dir[i][0];

36             q.y=p.y+dir[i][1];

37             q.z=p.z+dir[i][2];

38             q.step=p.step;

39             if(q.x<0||q.x>=n||q.y<0||q.y>=n||q.z<0||q.z>=n)

40                 continue;

41             if(visited[q.x][q.y][q.z]||map[q.x][q.y][q.z]=='X')

42                 continue;

43             visited[q.x][q.y][q.z]=true;

44             q.step=p.step+1;

45             Q.push(q);

46         }

47     }

48     return false;

49 }

50 

51 

52 int main(){

53     while(~scanf("%s%d",str,&n)){

54         for(int i=0;i<n;i++){

55             for(int j=0;j<n;j++){

56                 scanf("%s",map[i][j]);

57             }

58         }

59         scanf("%d%d%d",&sx,&sy,&sz);

60         scanf("%d%d%d",&ex,&ey,&ez);

61         scanf("%s",str);

62         map[ex][ey][ez]='O';//       ，             。。。

63         if(bfs()){

64             printf("%d %d
",n,ans);

65         }else 

66             puts("NO ROUTE");

67     }

68     return 0;

69 }