题目链接:http://icpc.njust.edu.cn/Problem/Hdu/2612/

题意:有两个人在地图上不同的位置,地图上由若干个餐厅,求两人能同时到达一个餐厅所用最少的总时间。

代码如下:

 #include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define inf 0x3f3f3f3f
#define maxn 205
int n,m,t;
char Map[maxn][maxn];
bool vis[maxn][maxn];
int a[][];
struct node{
int x,y,step;
};
node st,cur,nxt;
vector<node>p1;
vector<node>p2;
int dir[][]={,,,-,,,-,};
void bfs(int x,int y,vector<node> &p)
{
mem(vis,false);//记住放在bfs里面,该函数将会多次调用
queue<node>q;
st.x=x,st.y=y,st.step=;
q.push(st);
vis[x][y]=true;
while(!q.empty())
{
cur=q.front();
q.pop();
if(Map[cur.x][cur.y]=='@')
{
p.push_back(cur);//每个点只有一次机会进入队列,故vector中只有不同的'@'位置
}
f(i,,)
{
nxt=cur;
nxt.x+=dir[i][];
nxt.y+=dir[i][];
nxt.step++;
if(nxt.x<||nxt.x>n||nxt.y<||nxt.y>m||Map[nxt.x][nxt.y]=='#')continue;
if(vis[nxt.x][nxt.y])continue;
vis[nxt.x][nxt.y]=true;
q.push(nxt);
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
while(scanf("%d%d",&n,&m)==)
{
char c;
f(i,,n)
f(j,,m)
{
scanf(" %c",&Map[i][j]);
if(Map[i][j]=='Y')a[][]=i,a[][]=j;
if(Map[i][j]=='M')a[][]=i,a[][]=j;
}
p1.clear();
p2.clear();
bfs(a[][],a[][],p1);
bfs(a[][],a[][],p2);
int ans=inf;
f(i,,p1.size()-)
f(j,,p2.size()-)
{
if((p1[i].x==p2[j].x)&&(p1[i].y==p2[j].y))//到达同一个点
{
ans=min(ans,p1[i].step+p2[j].step);
// dbg(ans);
}
}
pf("%d\n",ans*); }
}

最新文章

  1. react native 的js 文件从哪里获取
  2. linux内核更新前后配置文件的比较
  3. linux服务之rsyslog
  4. XAML中的Path
  5. JPA学习---第十一节:JPA中的多对多双向关联实体定义与注解设置及操作
  6. mysql 在线修改表结构工具 gh-ost
  7. 《Two Days DIV + CSS》读书笔记——CSS选择器
  8. [置顶] Oracle GoldenGate 常见问题:长事务处理
  9. 博弈论之Nim游戏
  10. Scala学习笔记(一)
  11. Jenkins集成Docker镜像实现自动发布
  12. bzoj1073[SCOI2007]kshort
  13. PeopleSoft 后台更新密码
  14. js 金额补全处理
  15. superset链接本地mysql数据库
  16. 20165317Java实验三敏捷开发与XP实践
  17. MOG插件(葡萄牙语,略作翻译)
  18. C# Timer使用方法示例
  19. js排序算法02——插入排序
  20. excel 开头 结尾,中间 类似 SQL like ab% ,%ab ,%ab%

热门文章

  1. Python如何规避全局解释器锁(GIL)带来的限制
  2. JSON parse error: Cannot deserialize value of type `java.util.Date` from String
  3. 手写实现vue的MVVM响应式原理
  4. 【简单版】hexo博客搭建流程梳理
  5. C#中使用 正则表达式 替换img中src路径但保留图片名
  6. linux 下修改最大文件数
  7. Pycharm2019.2激活至2089年
  8. Java Web环境配置
  9. FCC 成都社区&#183;技术周刊 第 14 期
  10. iview2+ 表单密码验证