You play a new RPG. The world map in it is represented by a grid of n × m cells. Any playing character staying in some cell can move from this cell in four directions — to the cells to the left, right, forward and back, but not leaving the world map.
Monsters live in some cells. If at some moment of time you are in the cell which is reachable by some monster in d steps or less, he immediately runs to you and kills you.
You have to get alive from one cell of game field to another. Determine whether it is possible and if yes, find the minimal number of steps required to do it.
Input
The first line contains three non-negative integers n, m and d (2 ≤ n·m ≤ 200000, 0 ≤ d ≤ 200000) — the size of the map and the maximal distance at which monsters are dangerous.
Each of the next n lines contains m characters. These characters can be equal to «.», «M», «S» and «F», which denote empty cell, cell with monster, start cell and finish cell, correspondingly. Start and finish cells are empty and are presented in the input exactly once.
Output
If it is possible to get alive from start cell to finish cell, output minimal number of steps required to do it. Otherwise, output «-1».
Examples
Input
5 7 1 S.M...M ....... ....... M...M.. ......F
Output
12
Input
7 6 2 S..... ...M.. ...... .....M ...... M..... .....F
Output
11
Input
7 6 2 S..... ...M.. ...... ...... .....M M..... .....F
Output
-1
Input
4 4 2 M... .S.. .... ...F
Output
-1
Note
Please note that monsters can run and kill you on start cell and on finish cell as well.
题意：找起点S到终点F的最短路，怪物M在d步之内可以到达的点都是障碍。
思路：先把所有怪物加入队列同为起点，跑一遍bfs扩展d层停止，预处理出哪些点是障碍。然后跑一遍S到F的最短路。
这题有几个注意的地方：
1.预处理怪物如果用对于每个怪物分别dfs一次&&只用一种标记，那么wa，因为怪物a可能走到怪物b的附近把怪物b的路封掉，这样子的话，怪物b附近被封掉的点如果以b为起点，可以扩展更远，就被检查出已标记而不继续扩展了。这样会漏掉很多点。
2.如果用对于每个怪物分别dfs一次&&分别用不同标记，那么tle，正确性是没问题，但重复检查太多，超时。
3.如果用对于每个怪物分别bfs一次&&只用一种标记，那么wa，原因同第1点。
4.如果用对于每个怪物分别bfs一次&&分别用不同标记，那么tle，原因同第2点。
因此同时把所有怪物加入队列，跑一遍bfs。
存图用vector，判重用（第几行*列数+第几列）唯一编码。
bfs代码目前还不成风格，很丑而且容易丢东西出bug
#include<bits/stdc++.h>
using namespace std;
int n,m,d;
vector<int> a[200005];
map<int,bool> vis;
struct Node{
int r,c,d;
}s,t;
queue<Node> Q;
void init()
{
char str[200005];
scanf("%d%d%d",&n,&m,&d);
for(int i=0;i<n;i++)
{
scanf("%s",str);
for(int j=0;j<m;j++)
{
if(str[j]=='M')a[i].push_back(1);
else
{
a[i].push_back(0);
if(str[j]=='S')s=(Node){i,j,0};
else if(str[j]=='F')t=(Node){i,j,0};
}
}
}
}
bool inside(int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
void monster()
{
queue<Node> Q;
map<int,bool> vis;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(a[i][j])
{
vis[i*m+j]=1;
Q.push((Node){i,j,0});
}
while(!Q.empty())
{
Node u=Q.front();Q.pop();
Node v;
v.r=u.r+1;v.c=u.c;v.d=u.d+1;
if(inside(v.r,v.c)&& !vis[v.r*m+v.c]&&v.d<=d){Q.push(v);a[v.r][v.c]=1;vis[v.r*m+v.c]=1;}
v.r=u.r-1;
if(inside(v.r,v.c)&& !vis[v.r*m+v.c]&&v.d<=d){Q.push(v);a[v.r][v.c]=1;vis[v.r*m+v.c]=1;}
v.r=u.r;v.c=u.c+1;
if(inside(v.r,v.c)&& !vis[v.r*m+v.c]&&v.d<=d){Q.push(v);a[v.r][v.c]=1;vis[v.r*m+v.c]=1;}
v.c=u.c-1;
if(inside(v.r,v.c)&& !vis[v.r*m+v.c]&&v.d<=d){Q.push(v);a[v.r][v.c]=1;vis[v.r*m+v.c]=1;}
}
}
int bfs()
{
if(!a[s.r][s.c]){Q.push(s);vis[s.r*m+s.c]=1;}
while(!Q.empty())
{
Node u=Q.front();Q.pop();
if(u.r==t.r&&u.c==t.c)return u.d;
Node v;
v.r=u.r+1;v.c=u.c;v.d=u.d+1;
if(inside(v.r,v.c)&& !vis[v.r*m+v.c]&& 0==a[v.r][v.c]){Q.push(v);vis[v.r*m+v.c]=1;}
v.r=u.r-1;
if(inside(v.r,v.c)&& !vis[v.r*m+v.c]&& 0==a[v.r][v.c]){Q.push(v);vis[v.r*m+v.c]=1;}
v.r=u.r;v.c=u.c+1;
if(inside(v.r,v.c)&& !vis[v.r*m+v.c]&& 0==a[v.r][v.c]){Q.push(v);vis[v.r*m+v.c]=1;}
v.c=u.c-1;
if(inside(v.r,v.c)&& !vis[v.r*m+v.c]&& 0==a[v.r][v.c]){Q.push(v);vis[v.r*m+v.c]=1;}
}
return -1;
}
int main()
{
// freopen("input.in","r",stdin);
init();
monster();
cout<<bfs();
return 0;
}
京公网安备 11010502036488号