题目链接：http://codeforces.com/gym/101755/problem/H
题目分析：先bfs一遍怪兽可以到达的点，再bfs人可以走的地方看可不可以到达终点；
很显然读到 2<=n*m<=200000 时，就不可以用二维数组存图了，不过据说因为数据比较水，可以用vector存图；
vector存图AC代码：
/* */
# include <iostream>
# include <stdio.h>
# include <string.h>
# include <string>
# include <cmath>
# include <climits>
# include <cctype>
# include <ctime>
# include <algorithm>
# include <functional>
# include <bitset>
# include <set>
# include <map>
# include <deque>
# include <queue>
# include <stack>
# include <vector>
using namespace std; const int maxn=2e5+;
vector<char>mp[maxn];
vector<int>dis[maxn];
vector<int>vis[maxn];
int n, m; struct node
{
int x, y;
int step;
}cur, after; int dir[][]={{, }, {, -}, {, }, {-, }};
int sx, sy, fx, fy; int check(int x, int y)
{
if( x>= && x<n && y>= && y<m )
return ;
return ;
} void bfs1(int d)
{
queue<node>q;
int i, j;
for( i=; i<n; i++ )
{
for( j=; j<m; j++ )
{
if( mp[i][j]=='M' )
{
cur.x = i;
cur.y = j;
cur.step = ;
q.push(cur);
dis[i][j] = ;
}
}
} while( !q.empty() )
{
cur = q.front();
q.pop();
for(int i=; i<; i++ )
{
after.x = cur.x+dir[i][];
after.y = cur.y+dir[i][];
after.step = cur.step + ; if( check(after.x, after.y) )
{
if( !dis[after.x][after.y] && after.step<=d )
{
dis[after.x][after.y] = ;
q.push(after);
}
}
}
}
} void bfs2(int x, int y)
{
cur.x = x;
cur.y = y;
cur.step = ;
queue<node>q;
q.push(cur);
vis[x][y] = ;
if( dis[x][y] )
{
printf("-1\n");
return ;
}
while( !q.empty() )
{
cur = q.front();
q.pop();
if( mp[cur.x][cur.y]=='F' )
{
printf("%d\n", cur.step);
return ;
}
for(int i=; i<; i++ )
{
after.x = cur.x + dir[i][];
after.y = cur.y + dir[i][];
after.step = cur.step + ;
if( check(after.x, after.y) )
{
if( !dis[after.x][after.y] && !vis[after.x][after.y])
{
vis[after.x][after.y] = ;
q.push(after);
}
}
}
}
printf("-1\n");
return ;
}
int main()
{
int d, i, j;
cin>>n>>m>>d;
char s; for(i=; i<n; i++)
{
mp[i].clear();
vis[i].clear();
dis[i].clear();
} for(i=; i<n; i++ )
{
for(j=; j<m; j++ )
{
cin>>s;
mp[i].push_back(s);
dis[i].push_back();
vis[i].push_back();
}
}
bfs1(d); for(i=; i<n; i++ )
{
for( j=; j<m; j++ )
{
if( mp[i][j]=='F' )
{
fx = i;
fy = j;
}
if( mp[i][j]=='S' )
{
sx = i;
sy = j;
}
}
} if( dis[fx][fy] )
{
printf("-1\n");
}
else
{
bfs2(sx, sy);
}
return ;
}
这道题也让我知道了可以用一位数组存图：
详细的见代码注释：
AC代码：
/* */
# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <cctype>
# include <ctime>
# include <functional>
# include <cmath>
# include <bitset>
# include <deque>
# include <queue>
# include <stack>
# include <vector>
# include <set>
# include <map>
# include <climits>
using namespace std; typedef long long LL;
const int maxn=1e6+;
int n, m, t;
int a[maxn], d;
char str[maxn];
bool vis[maxn];///标记是否已经访问过
int dis[maxn];///记录步数
int dd[maxn];///dd[]为0,说明怪兽到不了,dd不为0说明怪兽可以到此处
int cnt, fx, fy, sx, sy;
int dir[][]={{, }, {, -}, {-, }, {, }};
struct node
{
int x;
int y;
}g[maxn], cur, after; bool check(int a, int b)
{
if( a>= && b>= && a<=n && b<=m && !dd[a*m+b] )
return true;
return false;
} void bfs()
{
queue<node>q;
cur.x = sx;
cur.y = sy;
vis[cur.x*m+cur.y] = ;
q.push(cur); while( !q.empty())
{
cur = q.front();
q.pop();
for(int i=; i<; i++ )
{
int xx = cur.x + dir[i][];
int yy = cur.y + dir[i][]; if( check(xx, yy) && !vis[xx*m+yy])
{
dis[xx*m+yy] = dis[cur.x*m+cur.y]+;
vis[xx*m+yy] = ;
after.x = xx;
after.y = yy;
q.push(after);
}
}
}
return ;
} void bfss()///广搜怪兽可以到达的地方
{
queue<node>q;
for(int i=; i<cnt; i++ )
q.push(g[i]); while( !q.empty() )
{
cur=q.front();
q.pop(); if( dd[cur.x*m+cur.y]== )
continue; for(int i=; i<; i++ )
{
int xx = cur.x + dir[i][];
int yy = cur.y + dir[i][];
if( check(xx, yy) )
{
after.x = xx;
after.y = yy;
dd[xx*m+yy] = dd[cur.x*m+cur.y]-;
q.push(after);
}
}
}
return ;
} int main()
{
while( ~ scanf("%d %d %d", &n, &m, &d) )
{
getchar();
for(int i=; i<=n; i++ )
scanf("%s", &str[i*m+]);///一维数组存图 memset(vis, false, sizeof(vis));
memset(dd, , sizeof(dd));
memset(dis, , sizeof(dis)); for(int i=; i<=n; i++ )
{
for(int j=; j<=m; j++ )
{
if( str[i*m+j]=='S' )
{
sx = i;
sy = j;
} else if( str[i*m+j]=='F' )
{
fx = i;
fy = j;
} else if( str[i*m+j]=='M' )
{
dd[i*m+j] = d+;
cur.x = i;
cur.y = j;
g[cnt++] = cur;
}
}
} bfss();
if( dd[sx*m+sy] || dd[fx*m+fy] )
{
printf("-1\n");
}
else
{
bfs();
if( !vis[fx*m+fy] )
printf("-1\n");
else
printf("%d\n", dis[fx*m+fy]);
}
}
return ;
}