Cod sursa(job #2546751)

Utilizator OvidRata Ovidiu Ovid Data 14 februarie 2020 14:23:21
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#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;
}