Pagini recente » Cod sursa (job #1044807) | Cod sursa (job #1695174) | Cod sursa (job #111747) | Cod sursa (job #2855433) | Cod sursa (job #2546751)
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ft first
#define sc second
ifstream fin("car.in"); ofstream fout("car.out");
int n, m, o[510][510], c[510][510];
pair<int ,int> S, F;
bool v[510][510];
void bfs(){
queue<pair<int, pair<int, int> > > q;
pair<int, pair<int, int> > f;
v[S.ft][S.sc]=true;
int Y[]={-1,-1, 0, 1, 1, 1, 0, -1};
int X[]={ 0, 1, 1, 1, 0,-1,-1, -1};
for(int i=0; i<8; i++){
int x=max(1, min(S.sc+X[i] ,m) ); int y=max(1, min(n, S.ft+Y[i]) );
if(o[y][x]==0){
if(!v[y][x] ){
q.push(mp(i, mp(y, x) ) );
c[y][x]=0;
v[y][x]=true;
}
}
}
//for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){cout<<c[i][j]<<" ";}cout<<"\n"; }cout<<"\n";
while(!q.empty()){
f=q.front(); q.pop();
for(int i=0; i<8; i++){
int x=max(1, min(f.sc.sc+X[i] ,m) ); int y=max(1, min(n, f.sc.ft+Y[i]) );
if(o[y][x]==0){
if(!v[y][x]){
v[y][x]=true;
c[y][x]=c[f.sc.ft][f.sc.sc]+min(abs( ((i)<1?8:i)-f.ft), 8-i+f.ft);
q.push(mp(i, mp(y, x))); cout<<i<<" "<<y<<" "<<x<<"\n";
}
else{
if( (c[f.sc.ft][f.sc.sc]+min(abs( ((i)<1?8:i)-f.ft), 8-i+f.ft))<c[y][x] ){
c[y][x]=c[f.sc.ft][f.sc.sc]+min(abs( ((i)<1?8:i)-f.ft), 8-i+f.ft);
q.push(mp(i, mp(y, x) )); cout<<i<<" "<<y<<" "<<x<<"\n";
}
}
for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){cout<<c[i][j]<<" ";}cout<<"\n"; }cout<<"\n";
}
}
}
}
//Y-first, X-second
int main(){
fin>>n>>m;
fin>>S.ft>>S.sc>>F.ft>>F.sc;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
fin>>o[i][j];
}
}
bfs();
cout<<c[F.ft][F.sc];
fout<<c[F.ft][F.sc];
return 0;
}