[关闭]
@xunuo 2017-04-21T19:37:55.000000Z 字数 2222 阅读 995

HDU 2102 A计划(三维)


Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

BFS


Description

可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主,因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚,告招天下勇士来拯救公主。不过公主早已习以为常,她深信智勇的骑士LJ肯定能将她救出。
现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口是S(0,0,0),公主的位置用P表示,时空传输机用#表示,墙用*表示,平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置,但如果被转到的位置是墙的话,那骑士们就会被撞死。骑士们在一层中只能前后左右移动,每移动一格花1时刻。层间的移动只能通过时空传输机,且不需要任何时间。

Input

输入的第一行C表示共有C个测试数据,每个测试数据的前一行有三个整数N,M,T。 N,M迷宫的大小N*M(1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况,后N*M表示迷宫第二层的布置情况。

Output

如果骑士们能够在T时刻能找到公主就输出“YES”,否则输出“NO”。

Sample Input

1
5 5 14
S*#*.
.#...
.....
****.
...#.

..*.P
#.*..
***..
...*.
*.#..

Sample Output

YES

解题思路:

一个BFS,但是要注意的是...他是一个三维的!!!!!它有两层楼。。。。
还有:只要遇到'#'都要传送;所以就可以特判一下:当当前位置为'#'且传送到的位置也是'#'或者是墙('*')时就将这个位置和传送的位置变为墙('*');
还有就是在vis初始化的时候要....唉。。。。

完整代码:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define inf 0x3f3f3f3f
  4. int dir[4][2]={0,1,0,-1,1,0,-1,0};
  5. int vis[15][15][2];
  6. char a[2][15][15];
  7. int n,m,t;///n行m列t秒
  8. int ans,flag;
  9. struct node
  10. {
  11. int x,y,z;
  12. int t;
  13. };
  14. int bfs()
  15. {
  16. queue<node>q;
  17. node now,next;
  18. now.x=0,now.y=0;
  19. now.z=0,now.t=0;
  20. flag=0;
  21. q.push(now);
  22. vis[now.x][now.y][now.z]=1;
  23. for(int i=0;i<2;i++)
  24. for(int j=0;j<n;j++)
  25. for(int k=0;k<m;k++)
  26. {
  27. if(i==0&&a[0][j][k]=='#'&&(a[1][j][k]=='*'||a[1][j][k]=='#'))
  28. {
  29. a[0][j][k]='*';
  30. a[1][j][k]='*';
  31. }
  32. if(i==1&&a[1][j][k]=='#'&&(a[0][j][k]=='*'||a[0][j][k]=='#'))
  33. {
  34. a[0][j][k]='*';
  35. a[1][j][k]='*';
  36. }
  37. }
  38. while(!q.empty())
  39. {
  40. now=q.front();
  41. q.pop();
  42. if(a[now.z][now.x][now.y]=='P')
  43. {
  44. ans=now.t;
  45. break;
  46. }
  47. for(int i=0;i<4;i++)
  48. {
  49. next.x=now.x+dir[i][0];
  50. next.y=now.y+dir[i][1];
  51. next.z=now.z;
  52. if(a[next.z][next.x][next.y]=='#'&&vis[next.x][next.y][next.z]==0)
  53. {
  54. if(next.z==0&&vis[next.x][next.y][next.z+1]==0)
  55. {
  56. vis[next.x][next.y][next.z]=1;
  57. next.t=now.t+1;
  58. next.z+=1;
  59. flag=1;
  60. }
  61. else if(next.z==1&&vis[next.x][next.y][next.z-1]==0)
  62. {
  63. vis[next.x][next.y][next.z]=1;
  64. next.t=now.t+1;
  65. next.z-=1;
  66. flag=1;
  67. }
  68. }
  69. if(a[next.z][next.x][next.y]!='*'&&vis[next.x][next.y][next.z]==0&&next.x>=0&&next.y>=0&&next.x<n&&next.y<m)
  70. {
  71. if(flag==1)
  72. flag=0;
  73. else
  74. next.t=now.t+1;
  75. q.push(next);
  76. vis[next.x][next.y][next.z]=1;
  77. }
  78. }
  79. }
  80. return ans;
  81. }
  82. int main()
  83. {
  84. int c;
  85. scanf("%d",&c);
  86. while(c--)
  87. {
  88. scanf("%d%d%d",&n,&m,&t);
  89. for(int j=0;j<2;j++)
  90. {
  91. for(int i=0;i<n;i++)
  92. {
  93. scanf("%s",a[j][i]);
  94. for(int k=0;k<m;k++)
  95. vis[i][k][j]=0;
  96. }
  97. }
  98. ans=inf;
  99. if(bfs()<=t)
  100. printf("YES\n");
  101. else
  102. printf("NO\n");
  103. }
  104. return 0;
  105. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注