题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2612 , 一道比较简单的广搜(BFS)题目。


算法:

  设置两个dist[][]数组,记录Y和M到几个KFC的距离,最后求两个dist的和的最小值即可。

  还有,Y是可以走M的位置的,同理,M也可以走Y的位置,不用纠结这个问题。有一点要注意的就是有的KFC是Y或M无法到达的,所以在最后求最小值的时候要注意这个KFC是否访问过。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF 1e8
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int MOD = ;
const int maxn = + ;
struct Pos {
int x , y;
};
Pos dir[] = {{- , } , { , } , { , } , { , -}};
vector <Pos> kfc;
int dist1[maxn][maxn] , dist2[maxn][maxn];
int vis[maxn][maxn] , dist[maxn][maxn];
char map[maxn][maxn];
int n , m; bool place(Pos a)
{
if(a.x < || a.y < || a.x >= n || a.y >= m || map[a.x][a.y] == '#' || vis[a.x][a.y])
return false;
return true;
}
void BFS(Pos start , int a[][maxn])
{
memset(vis , , sizeof(vis));
queue <Pos> que;
que.push(start);
vis[start.x][start.y] = ;
dist[start.x][start.y] = ;
while(!que.empty()) {
Pos u = que.front();
que.pop();
for(int i = ; i < ; i++) {
Pos tmp;
tmp.x = u.x + dir[i].x;
tmp.y = u.y + dir[i].y;
if(!place(tmp))
continue;
else {
que.push(tmp);
vis[tmp.x][tmp.y] = ;
dist[tmp.x][tmp.y] = dist[u.x][u.y] + ;
if(map[tmp.x][tmp.y] == '@')
a[tmp.x][tmp.y] = dist[tmp.x][tmp.y];
}
}
}
}
int main()
{
int i , j;
Pos start , end;
char ch;
while(~scanf("%d %d" , &n , &m))
{
memset(dist1 , , sizeof(dist1));
memset(dist2 , , sizeof(dist2));
kfc.clear();
for(i = ; i < n ; i++)
scanf("%s" , map[i]);
for(i = ; i < n ; i++) {
for(j = ; j < m ; j++) {
if(map[i][j] == 'Y') {
start.x = i;
start.y = j;
} else if(map[i][j] == 'M') {
end.x = i;
end.y = j;
} else if(map[i][j] == '@') {
Pos tmp = {i , j};
kfc.push_back(tmp);
}
}
}
BFS(start , dist1);
BFS(end , dist2);
int Min = INF;
for(i = ; i < kfc.size() ; i++) {
int x = kfc[i].x;
int y = kfc[i].y;
if(Min > dist1[x][y] + dist2[x][y] && dist1[x][y] && dist2[x][y])
Min = dist1[x][y] + dist2[x][y];
}
printf("%d\n" , * Min);
}
return ;
}

最新文章

  1. ESLint的使用笔记
  2. 14073102(CCDIKRecoil)
  3. 系统配置 之:远程桌面连接(win7系统)
  4. Log4cpp介绍及使用
  5. Flash图表控件FusionCharts如何定制图表中的趋势线和趋势区
  6. H3C远程登陆配置
  7. 高性能网络I/O框架-netmap源码分析
  8. ashx页面中context.Session[&quot;xxx&quot;]获取不到值的解决办法
  9. C++对象的销毁
  10. Elasticsearch-深入理解索引原理
  11. Java在Linux下 不能处理图形的解决办法 Can&#39;t connect to X11 window server
  12. sql_update
  13. excel数据导入mysql
  14. credential for git
  15. snmp监控f5
  16. maven项目,httpclient jar包冲突
  17. JS中的弹窗问题confirm和prompt
  18. 高级openg 混合,一个完整程序
  19. vjue 点击发送邮件如何处理
  20. 面试题21:包含min函数的栈

热门文章

  1. java线程基础知识----线程基础知识
  2. C++的STL总结(2)
  3. 猜拳游戏三局两胜------java实现代码
  4. SQL Server 2012 安装——安装 OR 卸载
  5. 51nod1035(循环节)
  6. 白白的(baibaide)——树状数组套主席树+splay
  7. 关于text-overflow实现&#183;多余字符省略&#183;的正确打开方式
  8. Swing实现canvas-nest.js 源码
  9. 73th LeetCode Weekly Contest Escape The Ghosts
  10. 华东交通大学2017年ACM“双基”程序设计竞赛 1008