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
| #include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int dr[4]{1,0,-1,0},dc[4]{0,1,0,-1};
int dt[2005][2005];
string mp[2005];
bitset<2005> v[2005];
struct position{
int r,c;
bool operator==(position a){
return r==a.r && c==a.c;
}
};
bool operator<(position a,position b){
return dt[a.r][a.c]>dt[b.r][b.c];
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,m,ans=INF;
cin>>n>>m;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) dt[i][j]=INF;
for(int i=0;i<n;i++){
cin>>mp[i];
}
position ps,pe;
cin>>ps.r>>ps.c;ps.r--;ps.c--;
cin>>pe.r>>pe.c;pe.r--;pe.c--;
dt[ps.r][ps.c]=0;
priority_queue<position> bfs;
bfs.push(ps);
int ct;
position now,next,mnPos;
while(!bfs.empty()){
now=bfs.top();
bfs.pop();
v[now.r][now.c]=1;
for(int i=0;i<4;i++){
next.r=now.r+dr[i];
next.c=now.c+dc[i];
if(next.r>=0 && next.c>=0 && next.r<n && next.c<m){
ct=dt[now.r][now.c];
if(mp[next.r][next.c]=='.')
ct++;
if(pe==next)
ans=min(ans,ct);
if(!v[next.r][next.c]){
v[next.r][next.c]=1;
dt[next.r][next.c]=ct;
bfs.push(next);
}
}
}
}
cout<<ans<<"\n";
return 0;
}
|