Pagini recente » Cod sursa (job #2969908) | Cod sursa (job #5383) | Cod sursa (job #460600) | Cod sursa (job #500707) | Cod sursa (job #2503654)
#include <bits/stdc++.h>
using namespace std;
ifstream f("barbar.in");
ofstream g("barbar.out");
const int N = 502;
const int oo = 1000000;
int dir[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}},cst[8][8];
int n, m, x, y, a[N][N];
queue<tuple<int, int, int>> q;
int main()
{
f >> n >> m;
vector<int> linie(m+1,oo);
vector<vector<int>> matrice(n+1,linie);
vector<vector<vector<int>>> c(8,matrice);
f>>x>>y;
for(int i=0;i<8;i++)
{
c[i][x][y]=0;
q.push(make_tuple(i,x,y));
}
f>>x>>y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f>>a[i][j];
for(int i=0;i<=n+1;i++)
a[i][0]=a[i][m+1]=1;
for(int j=1;j<=m;j++)
a[0][j]=a[n+1][j]=1;
for(int i=0;i<8;i++)cst[i][0]=cst[0][i]=min(i,8-i);
for(int i=1;i<8;i++)
for(int j=1;j<8;j++)
cst[i][j]=cst[i-1][j-1];
while(q.size())
{
int d, i, j, co, nextco, nexti, nextj, nextd;
tie(d,i,j)=q.front();
q.pop();
co=c[d][i][j];
for(nextd=0;nextd<8;nextd++)
{
nextco=co+cst[d][nextd];
nexti=i+dir[nextd][0];
nextj=j+dir[nextd][1];
if(!a[nexti][nextj])
if(nextco<c[nextd][nexti][nextj])
{
c[nextd][nexti][nextj]=nextco;
q.push(make_tuple(nextd,nexti,nextj));
}
}
}
int ans=oo;
for(int i=0;i<8;i++)
ans=min(ans,c[i][x][y]);
if(ans==oo)ans=-1;
g<<ans;
return 0;
}