BFS(最短路) HDU 2612 Find a way
2024-08-28 04:47:16
/*
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 ;
}
最新文章
- android开发虚拟机不能正常启动
- hibernate.hbm2ddl.auto配置详解
- C语言打印最长字符串
- python杂记-2(python之文件)
- MinHash算法-复杂度待整理
- CSS和JavaScript以及Ajax实现预加载图片的方法及优缺点分析
- Struts个人总结
- 【转】随身HiFi 安卓OTG功能在音频上的妙用
- cookie设置
- 算法提高 P1001
- 移动端1px问题处理方法
- 创建DVWA环境时遇到的问题
- hadoop学习笔记之一步一步部署hadoop分布式集群
- PHP配置方法
- MySQL缓存分类和配置
- golang学习笔记---函数、方法和接口
- [转载]ASP.NET伪静态页面的实现和伪静态在IIS7.0中的配置
- hdu 1556 Color the ball(树状数组)
- shell脚本中特定符合变量的含义
- yum源笔记
热门文章
- Spring Data JPA 中常用注解
- TCP/IP学习笔记(3)----IP,ARP,RARP协议
- JSP的会话(Session)跟踪
- 【.Net 学习系列】-- Windows服务定时运行,判断当前时间是否在配置时间段内
- Centos7最小安装下Install Clamav(2017-06-09最后更新)
- excel2010英文大写怎么变小写
- 初探FFT在数字图像处理中的应用(fft2函数的用法)
- 【C++/数据结构】单链表的基本操作
- scikit-learn:3.3. Model evaluation: quantifying the quality of predictions
- MVC 用户权限HttpContext.User.IsInRole()