也是一个走迷宫的问题,不过又有了点变化。

这里迷宫里有若干把火,而且火每秒也是向四个方向蔓延的。问人是否能走出迷宫。

我用了两遍BFS,第一遍把所有着火的格子加入队列,然后计算每个格子着火的时间。

第二遍便是走迷宫,只有当这个格子不是墙,而且当前时间在这个格子着火之前才能拓展。当然,并不是所有的空格都一定会着火。

 #include <cstdio>
#include <cstring>
#include <queue>
using namespace std; struct Node
{
int x, y, t;
Node(int x=, int y=, int t=):x(x), y(y), t(t) {}
}; Node st; const int maxn = + ;
int row, col;
char maze[maxn][maxn];
int time[maxn][maxn];
bool vis[maxn][maxn]; int dx[] = { , , , - };
int dy[] = { , , -, }; inline bool in(int x, int y)
{ return x >= && x < row && y >= && y < col; } inline bool border(int x, int y)
{ return x == || x == row- || y == || y == col-; } void init()
{
memset(time, -, sizeof(time));
queue<Node> Q;
for(int i = ; i < row; i++)
for(int j = ; j < col; j++)
{
if(maze[i][j] == 'F') { Q.push(Node(i, j, )); time[i][j] = ; }
if(maze[i][j] == 'J') { st.x = i; st.y = j; st.t = ; }
}
while(!Q.empty())
{
Node now = Q.front(); Q.pop();
for(int i = ; i < ; i++)
{
int x = now.x + dx[i];
int y = now.y + dy[i];
int t = now.t + ;
if(in(x, y) && time[x][y] < && maze[x][y] != '#')
{
Q.push(Node(x, y, now.t + ));
time[x][y] = t;
}
}
}
} int BFS()
{
memset(vis, false, sizeof(vis));
queue<Node> Q;
Q.push(st);
vis[st.x][st.y] = true;
while(!Q.empty())
{
Node now = Q.front(); Q.pop();
if(border(now.x, now.y)) return now.t + ;
for(int i = ; i < ; i++)
{
int x = now.x + dx[i];
int y = now.y + dy[i];
int t = now.t + ;
if(in(x, y) && !vis[x][y] && maze[x][y] != '#')
{
if(time[x][y] >= && time[x][y] <= t) continue;
vis[x][y] = true;
Q.push(Node(x, y, t));
}
}
}
return ;
} int main()
{
//freopen("in.txt", "r", stdin); int T; scanf("%d", &T);
while(T--)
{
scanf("%d%d", &row, &col);
for(int i = ; i < row; i++) scanf("%s", maze[i]);
init();
int ans = BFS();
if(ans) printf("%d\n", ans);
else puts("IMPOSSIBLE");
} return ;
}

代码君

最新文章

  1. 【Oracle 集群】ORACLE DATABASE 11G RAC 知识图文详细教程之缓存融合技术和主要后台进程(四)
  2. centos 研究
  3. Oracle中SQL查询表字段基本信息、主键、外键(转)
  4. Minecraft 插件 world edit 的cs 命令
  5. PoEdu - C++阶段班【Po学校】- Lesson03-4_构造函数&amp;赋值函数&amp;拷贝构造函数&amp;学习方式 - 第6天
  6. java 调用打印机 打印服务
  7. win10 UWP 标题栏后退
  8. 【62】Spring总结之bean(3)
  9. vue+axios完美实现前端路由拦截
  10. angularjs处理/n转&lt;br/&gt;时候 &lt;br/&gt;不会解析的问题
  11. vscode 的使用笔记
  12. linux软件管理 软件安装
  13. sqlalchemy 简介
  14. day55 jQuery 练习
  15. Oracle中SYS_CONNECT_BY_PATH函数的妙用 ;
  16. bzoj千题计划153:bzoj2431: [HAOI2009]逆序对数列
  17. js ajax post 提交的时候后台接收不到参数,但是代码没有错,怎么回事
  18. 最新的 Vue 相关开源项目库汇总
  19. 重复代码Duplicated Code---要重构的信号
  20. Visual Studio for Mac 安装时无法连接到网络等问题

热门文章

  1. JavaScript中this的工作原理以及注意事项
  2. 实现WMSservice的时候,出现边缘的点或icon被切断的情况
  3. 金融证券协议FIX/FAST/STEP
  4. 用于主题检测的临时日志(b42e98ba-eb4f-4099-a54c-7aee3f29c3dd - 3bfe001a-32de-4114-a6b4-4005b770f6d7)
  5. 初识IOS
  6. ZOJ3560 Re:the Princess(高斯消元法)
  7. ZOJ2928 Mathematical contest in modeling(模拟退火)
  8. POJ 1811 Prime Test (Pollard rho 大整数分解)
  9. 如何提高SQL的执行效率
  10. [RM HA3] Zookeeper在RM HA的应用