题目描述
The Barareh village is on fire due to the attack of the virtual enemy. Several places are already on fire and the fire is spreading fast to other places. Khorzookhan who is the only person remaining alive in the war with the virtual enemy,tries to rescue himself by reaching to the only helicopter in the Barareh villiage.
Suppose the Barareh village is represented by an n m grid. At the initial time, some grid cells are on fire. If a cell catches fire at time x, all its 8 vertex-neighboring cells will catch fire at time x + k. If a cell catches fire, it will be on fire forever.
At the initial time, Khorzookhan stands at cell s and the helicopter is located at cell t. At any time x, Khorzookhan can move from its current cell to one of four edge-neighboring cells, located at the left, right, top, or bottom of its current cell if that cell is not on fire at time x + 1. Note that each move takes one second.
Your task is to write a program to find the shortest path from s to t avoiding fire.
输入
There are multiple test cases in the input. The first line of each test case contains three positive integers n, m and k (1 ⩽ n, m, k ⩽ 100), where n and m indicate the size of the test case grid n m, and k denotes the growth rate of fire. The next n lines, each contains a string of length m, where the jth character of the ith line represents the cell (i, j) of the grid. Cells which are on fire at time 0, are presented by character “f”. There may exist no “f” in the test case.
The helicopter and Khorzookhan are located at cells presented by “t” and “s”, respectively. Other cells are filled by “-” characters. The input terminates with a line containing “0 0 0” which should not be processed.
输出
For each test case, output a line containing the shortest time to reach t from s avoiding fire. If it is impossible to reach t from s, write “Impossible” in the output.
样例输入
7 7 2
f——
-f—f-
—-f–
——f
—s—
t—-f-
3 4 1
t–f
–s-
2 2 1
st
f-
2 2 2
st
f-
0 0 0
样例输出
4
Impossible
Impossible
1
题意：给出一个n*m的地图，地图上f表示一个着火点，s表示人的初始位置，t表示终点位置，k值表示火的蔓延速度，每过k个单位时间，一个着火点将向四周八个方向蔓延一个格子。人可以上下左右移动，每移动一格用时一个单位时间，只要在人到达某个格子的那个时间点，那个格子没有着火，人就可以往那个格子行走。问人从起始点到达终点的最小时间是多少，若不能到达输出-1。
首先注意到给出的地图范围很小，只有100*100的大小。
于是我们考虑广搜，对于多个着火点的蔓延，因为每个时间地图的形式可能是不一样的，我们先广搜出地图上每个格子的预着火时间，到时在人广搜找路时即可直接对比时间判断在某个时间点是否可以走向某个格子。
处理完所有火的预计到达时间后，直接广搜人到达终点的最短时间，对于到达每个格子的状态，我们记录一个时间，用时间判断是否着火，并且若搜到了终点，直接输出第一次到达终点的时间，即最短时间。
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y,ti;
node() {};
node(int a,int b,int c)
{
x=a;
y=b;
ti=c;
}
};
int walkx[]= {1,1,1,-1,-1,-1,0,0};
int walky[]= {1,0,-1,0,-1,1,1,-1};
int px[]= {1,-1,0,0};
int py[]= {0,0,1,-1};
int n,m,k;
char mp[105][105];
int fire[108][108];
bool vis[108][108];
queue<node>q;
int main()
{
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
if(n==0&&m==0&&k==0)break;
node st,ed;
while(!q.empty())q.pop();
memset(fire,0x3f,sizeof(fire));
memset(vis,false,sizeof(vis));
for(int i=0; i<n; i++)
{
scanf("%s",mp[i]);
for(int j=0; j<m; j++)
{
if(mp[i][j]=='s')st.x=i,st.y=j,st.ti=0;
if(mp[i][j]=='t')ed.x=i,ed.y=j,ed.ti=0x3f3f3f3f;
if(mp[i][j]=='f')
{
fire[i][j]=0;
q.push(node(i,j,0));
vis[i][j]=true;
}
}
}
while(!q.empty())
{
node tmp=q.front();
q.pop();
for(int i=0; i<8; i++)
{
int tx=tmp.x+walkx[i];
int ty=tmp.y+walky[i];
if(tx>=0&&ty>=0&&tx<n&&ty<m&&vis[tx][ty]==false)
{
fire[tx][ty]=min(fire[tx][ty],tmp.ti+k);
q.push(node(tx,ty,tmp.ti+k));
vis[tx][ty]=true;
}
}
}
// for(int i=0;i<n;i++)
// for(int j=0;j<m;j++)
// printf("%d%c",fire[i][j],j==m-1?'
':' ');
memset(vis,false,sizeof(vis));
q.push(st);
vis[st.x][st.y]=true;
while(!q.empty())
{
node tmp=q.front();
q.pop();
for(int i=0; i<4; i++)
{
int tx=tmp.x+px[i];
int ty=tmp.y+py[i];
if(tx>=0&&ty>=0&&tx<n&&ty<m&&tmp.ti+1<fire[tx][ty]&&vis[tx][ty]==false)
{
if(tx==ed.x&&ty==ed.y) ed.ti=min(ed.ti,tmp.ti+1);
q.push(node(tx,ty,tmp.ti+1));
vis[tx][ty]=true;
}
}
if(vis[ed.x][ed.y])break;
}
if(ed.ti==0x3f3f3f3f)printf("Impossible
");
else printf("%d
",ed.ti);
}
}