hdu 2612 Find a way
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=2612
Find a way
Description
Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.
Input
The input contains multiple test cases.
Each test case include, first two integers $n, m. (2 \leq n,m \leq 200).$
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF
Output
For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.
Sample Input
4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#
Sample Output
66
88
66
两次bfs,注意若有一方无法到达某个kfc,这个点就不能取。。
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using std::min;
using std::cin;
using std::cout;
using std::endl;
using std::find;
using std::sort;
using std::map;
using std::pair;
using std::queue;
using std::vector;
using std::multimap;
#define pb(e) push_back(e)
#define sz(c) (int)(c).size()
#define mp(a, b) make_pair(a, b)
#define all(c) (c).begin(), (c).end()
#define iter(c) decltype((c).begin())
#define cls(arr,val) memset(arr,val,sizeof(arr))
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
const int N = ;
const int INF = ~0u >> ;
typedef unsigned long long ull;
char G[N][N];
int H, W, Sx, Sy, Dx, Dy, dist[][N][N];
const int dx[] = { , , -, }, dy[] = { -, , , };
struct Node {
int x, y;
Node(int i = , int j = ) :x(i), y(j) {}
}Y, M;
void bfs(int x, int y, bool d) {
queue<Node> q;
q.push(Node(x, y));
dist[d][x][y] = ;
while (!q.empty()) {
Node t = q.front(); q.pop();
rep(i, ) {
int nx = t.x + dx[i], ny = t.y + dy[i];
if (nx < || nx >= H || ny < || ny >= W) continue;
if (G[nx][ny] == '#' || dist[d][nx][ny]) continue;
dist[d][nx][ny] = dist[d][t.x][t.y] + ;
q.push(Node(nx, ny));
}
}
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
while (~scanf("%d %d", &H, &W)) {
cls(dist, );
vector<Node> kfc;
rep(i, H) {
scanf("%s", G[i]);
rep(j, W) {
if (G[i][j] == 'Y') Sx = i, Sy = j;
if (G[i][j] == 'M') Dx = i, Dy = j;
if (G[i][j] == '@') kfc.pb(Node(i, j));
}
}
bfs(Sx, Sy, ), bfs(Dx, Dy, );
int res = INF;
rep(i, sz(kfc)) {
Node &k = kfc[i];
int A = dist[][k.x][k.y], B = dist[][k.x][k.y];
if (!A || !B) continue;
res = min(res, A + B);
}
printf("%d\n", res * );
}
return ;
}
最新文章
- layer.open打开iframe页面的调用父页面方法及关闭
- VB编程的键盘控制
- WordPress数据库优化技巧
- fir.im Weekly - 如何打造真正的工程师文化
- [转]MySQL5.6新特性之Multi-Range Read
- JDBC读取新插入Oracle数据库Sequence值的5种方法
- php : 类常量
- Hibernate(三)——框架中的关系映射
- Android创建启动画面
- cocos2d-x游戏开发系列教程-搭建cocos2d-x的windows开发环境
- Android---->;RelativeLayout相对对齐方式布局
- Python四步实现决策树ID3算法,参考机器学习实战
- RHEL/Centos7 安装图形化桌面(转)
- 【原创】大叔问题定位分享(25)ambari metrics collector内置standalone hbase启动失败
- python自动化框架(一)
- upload三种上传方式(上)---Servlet---post---commons-fileupload.1.2.1.jar方式请求上传文件
- IntelliJ IDEA LicenseServer激活及使用
- Code First NotMapped
- java正则验证
- linux vi 删除一行,复制一行命令,删除所有空白行