直接上中文

Descriptions:

  1. 乔在迷宫中工作。不幸的是,迷宫的一部分着火了,迷宫的主人没有制定火灾的逃跑计划。请帮
    助乔逃离迷宫。根据乔在迷宫中的位置以及迷宫的哪个方块着火,你必须确定火焰烧到他之前,
    乔是否可以离开迷宫,如果能离开他能跑多快。
  2. 乔和火每分钟移动一个方格,上、下、左、右,四个方向中的一个。火势向四个方向同时蔓延。
    乔可以从迷宫的任何一个边界逃离迷宫。无论是乔还是火都不会到达有墙的位置。

输入

  1. 第一行输入包含一个整数,即测试次数
  2. 每个测试用例的第一行包含两个
  3. 整数RC,用空格分隔,1RC1000
  4. 下面R行中,每一行都包含C个字符,以及每个字符是以下之一:
  5. # 代表墙
  6. . 代表空地,火和乔是可通行的
  7. J 乔在迷宫中最初的位置,火和乔是可通行的
  8. F 代表火
  9. 在每组测试中只有一个J

输出

  1. 对于每个测试用例,如果在火蔓延的时候烧到了乔,则乔无法逃出迷宫,输出'IMPOSSIBLE'
    如果乔能逃出迷宫,则输出乔最快可以在几分钟内安全逃出迷宫,每组输出占一行

样例输入

  1. 2
  2. 4 4
  3. ####
  4. #JF#
  5. #..#
  6. #..#
  7. 3 3
  8. ###
  9. #J.
  10. #.F

样例输出

  1. 3
  2. IMPOSSIBLE

题目链接:

https://vjudge.net/problem/UVA-11624

注意火不止一个,火是固定的且火走过的地方时间也是一样的,所以可以先把火走的地方需要的时间处理一下,然后再对人bfs,多加一个条件,人在这个地方的时间要小于火在这个地方的时间

AC代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <deque>
  7. #include <vector>
  8. #include <queue>
  9. #include <string>
  10. #include <cstring>
  11. #include <map>
  12. #include <stack>
  13. #include <set>
  14. #include <sstream>
  15. #define mod 1000000007
  16. #define eps 1e-6
  17. #define ll long long
  18. #define INF 0x3f3f3f3f
  19. #define MEM(x,y) memset(x,y,sizeof(x))
  20. using namespace std;
  21. int T,n,m;
  22. char mp[1005][1005];//原始地图
  23. int visfire[1005][1005];//记录火是否烧过
  24. int vispeople[1005][1005];//记录人是否走过
  25. int firetime[1005][1005];//火经过这个地方的时间
  26. int peopletime[1005][1005];//人经过这个地方的时间
  27. int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1}};//四个方向
  28. struct node
  29. {
  30. int x,y;//坐标
  31. };
  32. node now,net;
  33. queue<node>fire;//两个队列 火和人
  34. queue<node>people;
  35. void judgetime()//预处理火经过的地方的时间
  36. {
  37. while(!fire.empty())
  38. {
  39. now=fire.front();
  40. fire.pop();
  41. for(int i=0; i<4; i++)//四种走法
  42. {
  43. int tx=now.x+dt[i][0];
  44. int ty=now.y+dt[i][1];
  45. if(tx>=0&&tx<n&&ty>=0&&ty<m&&!visfire[tx][ty]&&mp[tx][ty]!='#')
  46. {
  47. net.x=tx;
  48. net.y=ty;
  49. visfire[tx][ty]=1;//标记已烧过
  50. fire.push(net);//入队
  51. firetime[tx][ty]=firetime[now.x][now.y]+1;//时间加1
  52. }
  53. }
  54. }
  55. }
  56. void bfs()//
  57. {
  58. int f=0;
  59. while(!people.empty())
  60. {
  61. now=people.front();
  62. people.pop();
  63. if(now.x<=0||now.x>=n-1||now.y<=0||now.y>=m-1)//人走出来了
  64. {
  65. f=1;
  66. cout<<peopletime[now.x][now.y]+1<<endl;
  67. break;
  68. }
  69. for(int i=0; i<4; i++)//四种走法
  70. {
  71. net.x=now.x+dt[i][0];
  72. net.y=now.y+dt[i][1];
  73. if(net.x>=0&&net.x<n&&net.y>=0&&net.y<m&&!vispeople[net.x][net.y]&&mp[net.x][net.y]=='.'&&peopletime[now.x][now.y]+1<firetime[net.x][net.y])
  74. {
  75. vispeople[net.x][net.y]=1;//标记已走过
  76. people.push(net);//入队
  77. peopletime[net.x][net.y]=peopletime[now.x][now.y]+1;//时间+1
  78. }
  79. }
  80. }
  81. if(f==0)
  82. cout<<"IMPOSSIBLE"<<endl;
  83. }
  84. int main()
  85. {
  86. cin>>T;
  87. while(T--)
  88. {
  89. MEM(firetime,INF);//初始化
  90. MEM(peopletime,INF);
  91. MEM(visfire,0);
  92. MEM(vispeople,0);
  93. cin>>n>>m;
  94. for(int i=0; i<n; i++)
  95. {
  96. for(int j=0; j<m; j++)
  97. {
  98. cin>>mp[i][j];
  99. if(mp[i][j]=='J')
  100. {
  101. now.x=i;
  102. now.y=j;
  103. vispeople[i][j]=1;
  104. people.push(now);
  105. peopletime[i][j]=0;
  106. }
  107. if(mp[i][j]=='F')
  108. {
  109. now.x=i;
  110. now.y=j;
  111. visfire[i][j]=1;
  112. fire.push(now);
  113. firetime[i][j]=0;
  114. }
  115. }
  116. }
  117. judgetime();
  118. // for(int i=0; i<n; i++)
  119. // {
  120. // for(int j=0; j<m; j++)
  121. // {
  122. // cout<<firetime[i][j]<<" ";
  123. // }
  124. // cout<<endl;
  125. // }
  126. bfs();
  127. while(!fire.empty())//清空队列
  128. {
  129. fire.pop();
  130. }
  131. while(!people.empty())
  132. {
  133. people.pop();
  134. }
  135. }
  136. }

 

posted on 2019-07-03 11:23 Sky丨Star 阅读() 评论() 编辑 收藏

版权声明:本文为sky-stars原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/sky-stars/p/11125365.html