HDU2612(KB1-N)
2024-09-27 04:23:18
Find a way
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12795 Accepted Submission(s): 4105
Problem 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.
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<=n,m<=200).
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF
Each test case include, first two integers n, m. (2<=n,m<=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.
#...#
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#
Sample Output
66
88
66
88
66
Author
yifenfei
Source
//2017-02-28
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue> using namespace std; struct node{
int x, y, step;
void setNode(int x, int y, int step){
this->x = x;
this->y = y;
this->step = step;
}
};
char grid[][];
bool book[][];
int Ydis[][], Mdis[][];
int n, m;
int dx[] = {, , , -};
int dy[] = {, , -, };
const int inf = 0x3f3f3f3f; void bfs(int sx, int sy)
{
node tmp;
tmp.setNode(sx, sy, );
queue<node> q;
q.push(tmp);
memset(book, , sizeof(book));
book[sx][sy] = ;
int x, y, step;
while(!q.empty())
{
x = q.front().x;
y = q.front().y;
step = q.front().step;
q.pop();
if(grid[x][y] == '@'){
if(grid[sx][sy] == 'Y')Ydis[x][y] = step;
else Mdis[x][y] = step;
}
for(int i = ; i < ; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx>=&&nx<n&&ny>=&&ny<m&&!book[nx][ny]&&grid[nx][ny]!='#'){
book[nx][ny] = ;
tmp.setNode(nx, ny, step+);
q.push(tmp);
}
}
}
} int main()
{
while(cin>>n>>m)
{
for(int i = ; i < n; i++)
for(int j = ; j < m; j++)
cin>>grid[i][j];
memset(Ydis, inf, sizeof(Ydis));
memset(Mdis, inf, sizeof(Mdis));
for(int i = ; i < n; i++)
for(int j = ; j < m; j++)
if(grid[i][j] == 'Y' || grid[i][j] == 'M')
bfs(i, j);
int ans = inf;
for(int i = ; i < n; i++)
for(int j = ; j < m; j++)
if(grid[i][j] == '@' && ans > Ydis[i][j]+Mdis[i][j])
ans = Ydis[i][j] + Mdis[i][j];
cout<<*ans<<endl;
} return ;
}
最新文章
- OS存储管理——FIFO,LRU,OPT命中率
- Excel 行列转置 解决竖向拉,字母跟着递增的问题
- CSS Image Sprite--网页图片应用处理方式
- [iOS]如何给Label或者TextView赋HTML数据
- C# zip/unzip with DotNet framework 4.5
- SWOT分析法
- 如何使用git创建项目,创建分支
- POJ 2031 prim
- mysql date range
- 【转】Python 中 Iterator和Iterable的区别
- 201521123084 《Java程序设计》第14周学习总结
- inotify-tools + php脚本实现Linux服务器文件监控并邮件提醒
- bzoj 3680 吊打xxx 模拟退火
- win10x64 批处理自动安装打印机
- 二进制包安装MYSQL——
- Spring Cloud (6)A config 服务端配置 与github通信
- laravel 实现思路以及各组件原理
- hadoop学习笔记(六):HBase体系结构和数据模型
- CF993E:Nikita and Order Statistics(FFT)
- 《Java学习笔记JDK8》学习总结