/
hdu-2612.md
159 lines (132 loc) · 3.89 KB
/
hdu-2612.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
---
title: hdu-2612-Find a way（双 bfs）
date: 2018-07-23 12:34:42
lastmod: 2018-07-23 12:34:42
tags:
- ACM
- HDU
- 搜索
- C++
categories:
- ACM
---
[Find a way](http://acm.hdu.edu.cn/showproblem.php?pid=2612)
圣诞节要到了，坤神和瑞瑞这对基佬想一起去召唤师大峡谷开开车。百度地图一下，发现周围的召唤师大峡谷还不少，这对基佬纠结着，该去哪一个。坤神：我要去左边的这个（因为离自己比较近 哈哈~）。瑞瑞：我要去右边的这个（因为离自己比较近 嘿嘿~） ........ 这对基佬闹矛盾了，开车有危险了！为了不让他们去召唤师大峡谷坑人，riot 决定让他们去 X 召唤师大峡谷，保证他俩所走的路程和最短。每走一个点需要花费 11 分钟，输出他们一共花费多少时间（最短时间噢）
## Input
多组测试数据
每组数据，开始一行 n，m (2<=n,m<=200)
接下来是个 n x m 的矩阵
'Y' 表示坤神所在的初始位置
'M' 表示瑞瑞所在的初始位置
'#' 该点禁止通行
'.' 该点可通行
'@' 召唤师大峡谷
## Output
每组测试数据，输出坤神和瑞瑞到达同一个召唤师大峡谷所花费的最短时间。
## Sample Input
4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
@..M.
`#...#`
## Sample Output
66
88
66
## Hint
对于第一组样例，坤神和瑞瑞去矩阵（4,1）这个召唤师大峡谷，耗费的时间为 3 ✖️ 11 + 3 ✖️ 11 = 66，去矩阵（1,4）这个召唤师大峡谷，耗费的时间为 5 ✖️ 11 + 3 ✖️ 11 = 88。所以，最终答案：66。[思路参考](https://blog.csdn.net/ld_1090815922/article/details/72448569)
`写代码总是好粗心！！`
<!-- markdownlint-disable MD046 -->
```c++
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f //acm 中“无穷大”的一般定义
using namespace std;
const int M=202;
char mp[M][M]; //地图
int a[M][M],b[M][M];
bool vis[M][M]; //标记数组
int n,m;
int ans;
struct node
{
int x,y,step;
};
void init() //初始化函数
{
ans=inf;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
a[i][j]=inf;
b[i][j]=inf;
}
}
void bfs(int x,int y,bool flag){
int dir[4][2]={-1,0,1,0,0,1,0,-1};
node u,v;
queue<node> q; //初始化队列第一个元素
u.x=x;
u.y=y;
u.step=0;
vis[x][y]=true;
q.push(u);
while(!q.empty()){
u=q.front();
q.pop();
if(mp[u.x][u.y]=='@'){
if(!flag) a[u.x][u.y]=u.step;
else b[u.x][u.y]=u.step;
}
for(int i=0;i<4;i++){
int tx=u.x+dir[i][0];
int ty=u.y+dir[i][1];
if(tx>=0&&ty>=0&&tx<n&&ty<m&&!vis[tx][ty]&&mp[tx][ty]!='#'){//注意@和 M，Y 也是可以走的。
v.x=tx; //每次写搜索都忘记 vis!!!!
v.y=ty;
vis[tx][ty]=true; //我总是忘记。
v.step=u.step+1;
q.push(v);
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=0; i<n; i++)
scanf("%s",mp[i]);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
if(mp[i][j]=='Y')
{
memset(vis,false,sizeof(vis));
bfs(i,j,false);
}
if(mp[i][j]=='M')
{
memset(vis,false,sizeof(vis)); //记得再次初始化标记数组
bfs(i,j,true);
}
}
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(mp[i][j]=='@')
ans=min(ans,a[i][j]+b[i][j]);
printf("%d\n",ans*11);
}
return 0;
}
```