Pagini recente » Cod sursa (job #1879805) | Cod sursa (job #2821366) | Cod sursa (job #471239) | Cod sursa (job #1852270) | Cod sursa (job #2765314)
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll
ifstream fin("car.in"); ofstream fout("car.out");
#define cin fin
#define cout fout
int n, m, a[501][501];
struct edge{
int i=0, j=0, dr=0, d=0;
};
vector<edge> g[501][501][8];
int si, sj, fi, fj;
//0-1 bfs
struct nod{
int i=0, j=0, dr=0;
};
queue<nod> q[ 250010 ];
int d[501][501][8];
bool v[501][501][8];
void bfs(){
nod n0; n0.i=si, n0.j=sj;
for(int dr=0; dr<=7; dr++){
n0.dr=dr;
q[0].push(n0);
}
for(int D=0; D<=250000; D++){
while(!q[D].empty()){
auto f=q[D].front(); q[D].pop();
if( v[f.i][f.j][f.dr]==true ){continue;}
v[f.i][f.j][f.dr]=true;
d[f.i ][f.j][f.dr]=D;
for(auto e:g[f.i][f.j][f.dr]){
nod n0; n0.i=e.i, n0.j=e.j, n0.dr=e.dr; int d=e.d;
if(v[n0.i][n0.j][n0.dr]==true ){continue;}
q[D+d].push(n0);
}
}
}
}
int32_t main(){
INIT
cin>>n>>m;
cin>>si>>sj>>fi>>fj;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
char c;cin>>c;
a[i][j]=c-'0';
}
}
vector<int> X={1, 1, 0, -1, -1, -1, 0, 1};
vector<int> Y={0, -1,-1, -1, 0, 1, 1, 1};
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(a[i][j]==0){
for(int dr=1; dr<=8; dr++){
edge e; e.i=i, e.j=j, e.dr=dr%8, e.d=1;
g[i][j][dr-1].pb(e);
e.dr=dr-i;
g[i][j][dr%8].pb(e);
if( ( (X[dr%8]+j)<=m ) && ( (Y[dr%8]+i)<=n ) && ( a[ Y[dr%8]+i ][X[dr%8]+j ]==0 ) && ( (X[dr%8]+j)>=1 ) && ( (Y[dr%8]+i)>=1 ) ){
edge e; e.i=Y[dr%8]+i, e.j=X[dr%8]+j, e.dr=dr%8, e.d=0;
g[i][j][dr%8].pb(e);
}
}
}
}
}
bfs();
int res=1e9;
for(int dr=0; dr<=7; dr++){
res=min(res, d[fi][fj][dr]);
}
cout<<res<<"\n";
return 0;
}