题目链接：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 ;

 }

最新文章

  1. PS1应用之——修改linux终端命令行各字体颜色
  2. 理解SQL Server是如何执行查询的 (3/3)
  3. MySQL学习笔记01-MYSQL安装
  4. JavaScript学习记录总结（十）——几个重要的BOM对象
  5. poll实现
  6. boost/lexical_cast.hpp的简单使用方法_行动_新浪博客
  7. 基本排序算法&lt;一&gt;
  8. ubuntu12.04 安装中文输入法
  9. v-for并判断当前元素是否选中：$set实现响应添加属性
  10. elasticsearch-5.x JAVA API（001）
  11. 进入PE后不显示硬盘的解决办法
  12. explain和profiling分析查询SQL时间
  13. Go基础系列：读取标准输入
  14. EF设计模式之code first
  15. autoperfixer 版本配置
  16. RNN介绍，较易懂
  17. ocky勒索软件恶意样本分析2
  18. WordPress主题开发：优化标题
  19. ios成长之每日一遍(day 5)
  20. 安卓7.0拍照遇到 Uri暴露错误

热门文章

  1. c# 操作xml文件（读写）
  2. PowerShell命令批量添加、导出AD用户
  3. C# Java的加密的各种折腾
  4. elasticsearch授权访问
  5. 【一起学源码-微服务】Netflix Eureka 源码一：Netflix Eureka 源码初探，我们为什么要读源码？
  6. day27-python之迭代器协议
  7. Spring中抛出异常时，既要要返回错误信息，还要做事务回滚
  8. ssh无密码连接
  9. MySQL的My.cnf模板（转）
  10. 农业银行网上支付平台-商户接口编程-demo调试