尝试思路
首先考虑到有很多’@‘点，所以很容易想到的是 bfs 每个’@‘点，从中取出最小值即可。但是假设图中有很多’@'点，那么必定超时(200^4);
正确思路
从’Y’、‘M’开始 bfs，得到与每个’@‘的距离，再遍历每个’@'得出最小值即可.
给出代码
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
|
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LOCAL
#define cls ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define Mod 998244353
#define ll long long int
#define mset(a,b) memset(a,b,sizeof(a))
#define INF 1e9
const int maxn=2e2+5;
int vis[maxn][maxn];
int n,m;
string mp[maxn];
int mx,my;
int yx,yy;
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
int dis_y[maxn][maxn];
int dis_m[maxn][maxn];
struct node{
int x,y,step;
};
void bfsM(int x,int y){
mset(vis,0);
queue<node> q;
node st;
st.x=x;
st.y=y;
st.step=0;
q.push(st);
vis[x][y]=1;
node f,tmp;
while(!q.empty()){
f=q.front();
q.pop();
if(mp[f.x][f.y]=='@'){
dis_m[f.x][f.y]=f.step;
}
for(int i=0;i<4;i++){
int fx=f.x+dx[i];
int fy=f.y+dy[i];
if(fx>=0&&fx<n&&fy>=0&&fy<m&&!vis[fx][fy]&&mp[fx][fy]!='#'){
vis[fx][fy]=1;
tmp.x=fx;
tmp.y=fy;
tmp.step=f.step+1;
q.push(tmp);
}
}
}
}
void bfsY(int x,int y){
mset(vis,0);
queue<node> q;
node st;
st.x=x;
st.y=y;
st.step=0;
q.push(st);
vis[x][y]=1;
node f,tmp;
while(!q.empty()){
f=q.front();
q.pop();
if(mp[f.x][f.y]=='@'){
dis_y[f.x][f.y]=f.step;
}
for(int i=0;i<4;i++){
int fx=f.x+dx[i];
int fy=f.y+dy[i];
if(fx>=0&&fx<n&&fy>=0&&fy<m&&!vis[fx][fy]&&mp[fx][fy]!='#'){
vis[fx][fy]=1;
tmp.x=fx;
tmp.y=fy;
tmp.step=f.step+1;
q.push(tmp);
}
}
}
}
int main() {
cls;
#ifdef LOCAL
freopen("in.in","r",stdin);
#endif
while(cin>>n>>m){
for(int i=0;i<n;i++){
cin>>mp[i];
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(mp[i][j]=='Y'){
yx=i;
yy=j;
}
else if(mp[i][j]=='M'){
mx=i;
my=j;
}
}
mset(dis_m,-1);
mset(dis_y,-1);
bfsM(mx,my);
bfsY(yx,yy);
int ans=INF;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mp[i][j]=='@'&&dis_m[i][j]!=-1&&dis_y[i][j]!=-1){
ans=min(ans,dis_m[i][j]+dis_y[i][j]);
}
}
}
cout<<ans*11<<endl;
}
return 0;
}
|
