前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Hdu 2612 Find a Way(双点bfs)

Hdu 2612 Find a Way(双点bfs)

作者头像
Ch_Zaqdt
发布2019-01-10 11:13:31
2520
发布2019-01-10 11:13:31
举报
文章被收录于专栏:Zaqdt_ACM

       题意代码最后的注释里有,这道题就是对两个人分别进行bfs搜索,然后记录下这两个人到每一家KFC的步数,最后遍历地图求出最少的步数,思路很简单,但实现起来可能不是很好想。

AC代码:

代码语言:javascript
复制
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
#define MIN(a,b) a>b?b:a
const int MAX = 0x3f3f3f3f;
const int MAXN = 205;
struct Node {
  int x,y,step;
}Now,Next,S;
char MAP[MAXN][MAXN];
int vis[MAXN][MAXN];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int dis[MAXN][MAXN][2];                 // 用于标记两个人到KFC的路程
int flag,n,m;             // 用flag标记两个人

void bfs(){
  queue<Node> q;
  S.step = 0;
  memset(vis,0,sizeof(vis));
  q.push(S);
  while(!q.empty()){
    Now = q.front();
    q.pop();
    for(int i=0;i<4;i++){
      Next.x = Now.x + dir[i][0];
      Next.y = Now.y + dir[i][1];
      if(Next.x >= 0 && Next.y >= 0 && Next.x < n && Next.y < m && MAP[Next.x][Next.y] != '#' && vis[Next.x][Next.y] == 0){
        vis[Next.x][Next.y] = 1;
        Next.step = Now.step + 1;
        if(MAP[Next.x][Next.y]=='@'){
          dis[Next.x][Next.y][flag] = MIN(dis[Next.x][Next.y][flag],Next.step);           // 记录当前的步数
        }
        q.push(Next);
      }
    }
  }
  return ;
}
int main()
{
  while(~scanf("%d%d",&n,&m)){
    memset(dis,MAX,sizeof(dis));            // 记得初始化为最大值
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        cin>>MAP[i][j];
      }
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(MAP[i][j]=='Y'){
          flag = 0;            // 表示Y
          S.x = i;
          S.y = j;
          bfs();
        }
        if(MAP[i][j]=='M'){
          flag = 1;            // 表示M
          S.x = i;
          S.y = j;
          bfs();
        }
      }
    }
    int Min = MAX;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(MAP[i][j] == '@' && Min > (dis[i][j][0] + dis[i][j][1])){   // 遍历找出最短路
          Min = dis[i][j][0] + dis[i][j][1];
        }
      }
    }
    printf("%d\n",Min*11);
  }
  return 0;
}
/***
   [来源] Hdu 2612
   [题目] Find a Way
   [大意]
      就是两个人要去吃KFC,然而KFC有两个(也可以有多个),问他们两个人去哪家KFC,能让他俩走的路程最短(结果乘11)
   [输入]
      4 4
      Y.#@
      ....
      .#..
      @..M
      4 4
      Y.#@
      ....
      .#..
      @#.M
      5 5
      Y..@.
      .#...
      .#...
      @..M.
      #...#
   [输出]
      66
      88
      66
*/
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年02月06日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档