Pagini recente » Cod sursa (job #276495) | Cod sursa (job #483755) | Cod sursa (job #1212533) | Cod sursa (job #424469) | Cod sursa (job #3191831)
#include <bits/stdc++.h>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
ifstream fin ("car.in");
ofstream fout ("car.out");
const int NMAX=5e2+5;
const int INF=2e9;
int di[]={1,1,1,0,-1,-1,-1,0};
int dj[]={1,0,-1,-1,-1,0,1,1};
struct elem{
int x;
int y;
int c;
int d;
};
int dp[NMAX][NMAX][10];
bool a[NMAX][NMAX];
queue<elem>q[2];
int n,m;
bool intmat(int i,int j)
{
return 1<=i && 1<=j && i<=n && j<=m;
}
void bfs(int x1,int y1)
{
int i,j,dir;
for(dir=0;dir<8;dir++)
q[0].push({x1,y1,0,dir});
while(!q[0].empty())
{
while(!q[0].empty())
{
elem p=q[0].front();
q[0].pop();
elem aux;
aux.x=p.x+di[p.d];
aux.y=p.y+dj[p.d];
aux.c=p.c;
aux.d=p.d;
if(intmat(aux.x,aux.y) && a[aux.x][aux.y]==0 && dp[aux.x][aux.y][aux.d]>aux.c)
{
dp[aux.x][aux.y][aux.d]=aux.c;
q[0].push(aux);
}
aux.x=p.x;
aux.y=p.y;
aux.c=p.c+1;
aux.d=(p.d+1)%8;
if(intmat(aux.x,aux.y) && a[aux.x][aux.y]==0 && dp[aux.x][aux.y][aux.d]>aux.c)
{
dp[aux.x][aux.y][aux.d]=aux.c;
q[1].push(aux);
}
aux.d=(p.d+7)%8;
if(intmat(aux.x,aux.y) && a[aux.x][aux.y]==0 && dp[aux.x][aux.y][aux.d]>aux.c)
{
dp[aux.x][aux.y][aux.d]=aux.c;
q[1].push(aux);
}
}
while(!q[1].empty())
{
elem p=q[1].front();
q[0].push(p);
q[1].pop();
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
int x1,x2,y1,y2,i,j,dir,best=INF;
fin>>n>>m>>x1>>y1>>x2>>y2;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
fin>>a[i][j];
for(dir=0;dir<8;dir++)
dp[i][j][dir]=INF;
}
}
bfs(x1,y1);
for(dir=0;dir<8;dir++)
best=min(best,dp[x2][y2][dir]);
if(best==INF)
fout<<-1;
else
fout<<best;
return 0;
}