题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2612

思路:

裸的BFS,对于Y,M分别进行BFS,求出其分别到达各个点的最小时间;

然后对于@的点,将两者的最小时间相加即为到达此点的总时间,遍历所有@点,更新结果即可;

代码:

 #include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
#define MAX 0x7f7f7f7f
using namespace std;
int n,m;
int startY_x,startY_y;
int startM_x,startM_y;
char map[][];
int d[][]={,,-,,,,,-};
int vis1[][];
int vis2[][];
class node
{
public:
int x;
int y;
int time;
}cur,next;
queue<node>q;
bool Jude(int x,int y)
{
if(x<||x>=n||y<||y>=m||map[x][y]=='#')
return false;
return true;
}
void init()
{
for(int i=;i<;i++)
for(int j=;j<;j++)
{
vis1[i][j]=;
vis2[i][j]=;
} }
void bfs(int key)
{
while(!q.empty())
{
cur=q.front();
q.pop();
for(int i=;i<;i++)
{
int x=cur.x+d[i][];
int y=cur.y+d[i][];
if(!Jude(x,y)) continue;
if(key==)
{
if(vis1[x][y]) continue;
next.x=x;
next.y=y;
next.time=cur.time+;
vis1[x][y]=next.time;
q.push(next);
}
if(key==)
{
if(vis2[x][y]) continue;
next.x=x;
next.y=y;
next.time=cur.time+;
vis2[x][y]=next.time;
q.push(next);
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='Y')
{
startY_x=i;
startY_y=j;
}
if(map[i][j]=='M')
{
startM_x=i;
startM_y=j;
}
}
} cur.x=startY_x;
cur.y=startY_y;
cur.time=;
vis1[cur.x][cur.y]=;
q.push(cur);
bfs(); while(!q.empty()) q.pop();
cur.x=startM_x;
cur.y=startM_y;
cur.time=;
vis2[cur.x][cur.y]=;
q.push(cur);
bfs(); long long ans=MAX;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
{
if(map[i][j]=='@' && vis1[i][j] && vis2[i][j])
{
long long temp=vis1[i][j]+vis2[i][j];
ans=min(ans,temp);
}
}
cout<<ans*<<endl;
}
return ;
}

最新文章

  1. Zabbix监控VMare Vcenter
  2. [Python] Python 之 __new__() 方法与实例化
  3. mysql 基于lvm快照的备份
  4. Centos6.4编译安装Node.js(已验证)
  5. Python学习教程(learning Python)--3.3.2 Python的关系运算
  6. Oracle内存组件理论篇一
  7. Spring Quartz结合Spring mail定期发送邮件
  8. 阻止JS事件冒泡传递(cancelBubble 、stopPropagation)
  9. 利用Java泛型实现简单的泛型方法
  10. Lenghth of Last Word
  11. Spring Boot 主类及目录结构介绍
  12. Spring-WebSocket 教程
  13. 如何写Emit代码
  14. java线程学习之线程创建
  15. win10系统安装web3js的正确方法(2)
  16. redis 基础应用
  17. shell邮件发送功能实现
  18. 给data设置数据
  19. [CEOI2017]Building Bridges
  20. [经验]PLSQL乱码解决

热门文章

  1. websocket 项目应用
  2. 实现一个自己的promise
  3. Angular4.0.0发布总览文章
  4. 锋利的jQuery(1)——DOM对象与jQuery对象的转换
  5. 【 js 基础 】 深浅拷贝
  6. scss实现不同方向的三角
  7. JavaScript变量相关问题
  8. Select()和SelectMany()的区别
  9. Python open()
  10. XISE菜刀V21.0 官网版 XISE菜刀VIP破解版 XISE官网