Cod sursa(job #2642250)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 14 august 2020 10:50:33
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;ifstream fin("car.in");ofstream fout("car.out");int n,m,xi,yi,xf,yf,matrix[505][505],lung[505][505][8];int dx[]={-1,-1,0,1,1,1,0,-1};int dy[]={0,1,1,1,0,-1,-1,-1};struct triplet{int x,y,dir;};deque<triplet>coada;bool Valid(int i,int j,int dir){return i>=1&&j>=1&&i<=n&&j<=m&&matrix[i][j]==0;}int main(){fin>>n>>m>>xi>>yi>>xf>>yf;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){fin>>matrix[i][j];for(int k=0;k<8;++k){lung[i][j][k]=1e9;}}}for(int k=0;k<8;++k){lung[xi][yi][k]=1;coada.push_front({xi,yi,k});}while(!coada.empty()){int x=coada.front().x,y=coada.front().y,dir=coada.front().dir;if(x==xf&&y==yf){fout<<lung[x][y][dir]-1;return 0;}coada.pop_front();int xx=x+dx[dir];int yy=y+dy[dir];if(Valid(xx,yy,dir)&&lung[xx][yy][dir]>lung[x][y][dir]){lung[xx][yy][dir]=lung[x][y][dir];coada.push_front({xx,yy,dir});}int dir2=(dir+1)%8;if(lung[x][y][dir2]>1+lung[x][y][dir]){lung[x][y][dir2]=1+lung[x][y][dir];coada.push_back({x,y,dir2});}dir2=(dir+7)%8;if(lung[x][y][dir2]>1+lung[x][y][dir]){lung[x][y][dir2]=1+lung[x][y][dir];coada.push_back({x,y,dir2});}}fout<<-1;return 0;}