题目传送门

 /*
BFS:和UVA_11624差不多,本题就是分别求两个点到KFC的最短路,然后相加求最小值
*/
/************************************************
Author :Running_Time
Created Time :2015-8-4 19:36:36
File Name :HDOJ_2612.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 2e2 + ;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + ;
char maze[MAXN][MAXN];
bool vis[MAXN][MAXN];
int step[MAXN][MAXN];
int step2[MAXN][MAXN];
int dx[] = {-, , , };
int dy[] = {, , -, };
int n, m;
int sx, sy, ex, ey; bool judge_y(int x, int y) {
if (x < || x > n || y < || y > m || maze[x][y] == '#' || vis[x][y]) return false;
return true;
} bool judge_m(int x, int y) {
if (x < || x > n || y < || y > m || maze[x][y] == '#' || vis[x][y]) return false;
return true;
} void BFS_Y(void) {
memset (step, , sizeof (step));
memset (vis, false, sizeof (vis));
queue<pair<int, int> > Q; Q.push (make_pair (sx, sy));
vis[sx][sy] = true; step[sx][sy] = ;
while (!Q.empty ()) {
int x = Q.front ().first, y = Q.front ().second; Q.pop ();
for (int i=; i<; ++i) {
int tx = x + dx[i], ty = y + dy[i];
if (!judge_y (tx, ty)) continue;
Q.push (make_pair (tx, ty)); vis[tx][ty] = true;
step[tx][ty] = step[x][y] + ;
}
}
} void BFS_M(void) {
memset (vis, false, sizeof (vis));
memset (step2, , sizeof (step2));
queue<pair<int, int> > Q; Q.push (make_pair (ex, ey));
vis[ex][ey] = true; step2[ex][ey] = ;
while (!Q.empty ()) {
int x = Q.front ().first, y = Q.front ().second; Q.pop ();
for (int i=; i<; ++i) {
int tx = x + dx[i], ty = y + dy[i];
if (!judge_m (tx, ty)) continue;
step2[tx][ty] = step2[x][y] + ;
Q.push (make_pair (tx, ty)); vis[tx][ty] = true;
}
}
} int main(void) { //HDU 2612 Find a way
while (scanf ("%d%d", &n, &m) == ) {
for (int i=; i<=n; ++i) {
scanf ("%s", maze[i] + );
for (int j=; j<=m; ++j) {
if (maze[i][j] == 'Y') sx = i, sy = j;
if (maze[i][j] == 'M') ex = i, ey = j;
}
}
BFS_Y (); BFS_M ();
int ans = INF;
for (int i=; i<=n; ++i) {
for (int j=; j<=m; ++j) {
if (maze[i][j] == '@' && vis[i][j]) {
ans = min (ans, step[i][j] + step2[i][j]);
}
}
}
if (ans == INF) puts ("-1");
else printf ("%d\n", ans * );
} return ;
}

最新文章

  1. android开发虚拟机不能正常启动
  2. hibernate.hbm2ddl.auto配置详解
  3. C语言打印最长字符串
  4. python杂记-2(python之文件)
  5. MinHash算法-复杂度待整理
  6. CSS和JavaScript以及Ajax实现预加载图片的方法及优缺点分析
  7. Struts个人总结
  8. 【转】随身HiFi 安卓OTG功能在音频上的妙用
  9. cookie设置
  10. 算法提高 P1001
  11. 移动端1px问题处理方法
  12. 创建DVWA环境时遇到的问题
  13. hadoop学习笔记之一步一步部署hadoop分布式集群
  14. PHP配置方法
  15. MySQL缓存分类和配置
  16. golang学习笔记---函数、方法和接口
  17. [转载]ASP.NET伪静态页面的实现和伪静态在IIS7.0中的配置
  18. hdu 1556 Color the ball(树状数组)
  19. shell脚本中特定符合变量的含义
  20. yum源笔记

热门文章

  1. Spring Data JPA 中常用注解
  2. TCP/IP学习笔记(3)----IP,ARP,RARP协议
  3. JSP的会话(Session)跟踪
  4. 【.Net 学习系列】-- Windows服务定时运行,判断当前时间是否在配置时间段内
  5. Centos7最小安装下Install Clamav(2017-06-09最后更新)
  6. excel2010英文大写怎么变小写
  7. 初探FFT在数字图像处理中的应用(fft2函数的用法)
  8. 【C++/数据结构】单链表的基本操作
  9. scikit-learn:3.3. Model evaluation: quantifying the quality of predictions
  10. MVC 用户权限HttpContext.User.IsInRole()