Fire uva 11624

题目连接:http://acm.hust.edu.cn/vjudge/problem/28833

/*
首先对整个图bfs一次得到火焰燃烧的时刻表
之后在bfs搜路径时加一个火烧表的判断
坑点在于:如果时刻表等于0应该是从未烧过。。。如果不加以区分就会wa
*/
#include <bits/stdc++.h>
#define scan(x) scanf("%d",&x)
#define M(x) memset(x,0,sizeof(x))
#define REF(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int Max=1e3+;
char mat[Max][Max];
int book[Max][Max];
int vis[Max][Max];
int n,m,stx,sty;
struct node
{
int x,y,step;
node(){x=y=step=;}
node(int xx,int yy,int ss):x(xx),y(yy),step(ss){}
};
int nex[][]={,,,,,-,-,};
queue<node>que1;
void bfs1()
{
M(book);M(vis);
node u,v;
while(!que1.empty())
{
u=que1.front();
que1.pop();
for(int k=;k<;k++)
{
v.x=u.x+nex[k][];
v.y=u.y+nex[k][];
v.step=u.step+;
if(v.x<||v.y<||v.x>n||v.y>m) continue;
if(mat[v.x][v.y]=='#') continue;
if(book[v.x][v.y]) continue;
book[v.x][v.y]=v.step;
que1.push(v);
}
}
}
int bfs2()
{
M(vis);
queue<node>que;
node u,v;
que.push(node(stx,sty,));
vis[stx][sty]=;
while(!que.empty())
{
u=que.front();
que.pop();
for(int k=;k<;k++)
{
v.x=u.x+nex[k][];
v.y=u.y+nex[k][];
v.step=u.step+;
if(v.x<||v.y<||v.x>n||v.y>m) return v.step;
if(book[v.x][v.y]!=&&book[v.x][v.y]<=v.step) continue;//book[i][j]!=0
if(mat[v.x][v.y]=='#'||mat[v.x][v.y]=='F') continue;//不能把从未着火的点也排除
if(vis[v.x][v.y]) continue;
vis[v.x][v.y]=;
que.push(v);
}
}
return -;
}
int main()
{
int T;
for(scan(T);T;T--)
{
cin>>n>>m;getchar();
while(!que1.empty()) que1.pop();
REF(i,n)
{
REF(j,m)
{
scanf("%c",&mat[i][j]);
if(mat[i][j]=='J') stx=i,sty=j;
if(mat[i][j]=='F') que1.push(node(i,j,));
}
getchar();
}
bfs1();
int ans=bfs2();
if(ans!=-) cout<<ans<<endl;
else cout<<"IMPOSSIBLE"<<endl;
}
return ;
}
上一篇:vim 命令整理(自己经常使用)


下一篇:Position属性四个值:static、fixed、absolute和relative的区别和用法