#include"cstdio"
#include"queue"
#include"cstring"
using namespace std;
const int MAXN=;
const int INF=0X7fffffff;
typedef pair<int,int> P;
char mp[MAXN][MAXN];
int ft[MAXN][MAXN];
int jt[MAXN][MAXN];
int dx[]={,,-,};
int dy[]={,,,-};
int n,m;
int sy,sx;
void bfs1()//第一次广搜确定 fire到达passable square的时间
{
queue<P> que;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
{
ft[i][j]=INF;
if(mp[i][j]=='F')
{
que.push(P(i,j));
ft[i][j]=;
}
}
while(!que.empty())
{
P now = que.front();que.pop();
for(int i=;i<;i++)
{
int ny=now.first+dy[i];
int nx=now.second+dx[i];
if(<=ny&&ny<n&&<=nx&&nx<m&&mp[ny][nx]!='#')
{
int dist=ft[now.first][now.second]+;
if(dist<ft[ny][nx])
{
ft[ny][nx]=dist;
que.push(P(ny,nx));
}
}
}
}
}
void bfs2()
{
memset(jt,-,sizeof(jt));
queue<P> que;
que.push(P(sy,sx));
jt[sy][sx]=;
while(!que.empty())
{
P now=que.front();que.pop();
if(now.first==||now.first==n-||now.second==||now.second==m-)
{
printf("%d\n",jt[now.first][now.second]+);//逃出迷宫,注意+1
return ;
}
for(int i=;i<;i++)
{
int ny=now.first+dy[i];
int nx=now.second+dx[i];
if(<=ny&&ny<n&&<=nx&&nx<m&&mp[ny][nx]!='#'&&jt[ny][nx]==-)
{
int dist=jt[now.first][now.second]+;
if(dist<ft[ny][nx])//若在该时刻该点没有火焰到达说明可行
{
jt[ny][nx]=dist;
que.push(P(ny,nx));
}
}
}
} printf("IMPOSSIBLE\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
scanf("%*c");
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
scanf("%c",&mp[i][j]);
if(mp[i][j]=='J')
{
sy=i,sx=j;
}
}
scanf("%*c");
}
bfs1();
bfs2();
} return ;
}

最新文章

  1. iOS开发UI篇—CALayer简介
  2. rebuild new environment for DW step
  3. [推荐]移动H5前端性能优化指南
  4. jQuery动画流程分析
  5. 【iis错误码】IIS 服务 这些年遇到的错误码
  6. C# 时间函数
  7. Unity3D之Mecanim动画系统学习笔记(八):Animator Layers(动画分层)
  8. MITK-Qt4.8.4(x64)+VS2012+Win7_X64 编译记录
  9. PHPFarm - How to run multiple versions of PHP on the same computer
  10. iOS开发- 界面传值(1)-通知模式(广播)
  11. [Swust OJ 404]--最小代价树(动态规划)
  12. hdu4620 Fruit Ninja Extreme
  13. ajax 假上传文件
  14. 阿里Dubbo疯狂更新,关Spring Cloud什么事?
  15. width和max-width的用处
  16. anaconda中安装mmdetection
  17. MAC Homebrew安装和简单使用
  18. epoch、 iteration和batchsize区别
  19. memcached安装报错 error while loading shared libraries: libevent-2.0.so.5: cannot open shared object file: No such file or directory解决
  20. Vue属性中带’-‘的处理方式

热门文章

  1. 在jsp中嵌入javascript代码执行对html的影响方式
  2. 洛谷 P3216 [HNOI2011]数学作业
  3. Centos设置开机启动Apache和Mysql
  4. 第一个Spring Boot程序启动报错了
  5. ABAP制作密码输入框
  6. 第10条:尽量用enumerate取代range
  7. curl使用说明
  8. spring 注解事务
  9. Java多线程系列 面试题
  10. php 实现简单抽奖