hdu2612 Find a way BFS
2024-10-18 14:16:32
题目链接: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 ;
}
最新文章
- Zabbix监控VMare Vcenter
- [Python] Python 之 __new__() 方法与实例化
- mysql 基于lvm快照的备份
- Centos6.4编译安装Node.js(已验证)
- Python学习教程(learning Python)--3.3.2 Python的关系运算
- Oracle内存组件理论篇一
- Spring Quartz结合Spring mail定期发送邮件
- 阻止JS事件冒泡传递(cancelBubble 、stopPropagation)
- 利用Java泛型实现简单的泛型方法
- Lenghth of Last Word
- Spring Boot 主类及目录结构介绍
- Spring-WebSocket 教程
- 如何写Emit代码
- java线程学习之线程创建
- win10系统安装web3js的正确方法(2)
- redis 基础应用
- shell邮件发送功能实现
- 给data设置数据
- [CEOI2017]Building Bridges
- [经验]PLSQL乱码解决