Pagini recente » Diferente pentru fmi-no-stress-2012/solutii/parantezare intre reviziile 5 si 4 | Profil pop_oana1324 | Istoria paginii utilizator/mironica_vasile | Monitorul de evaluare | Cod sursa (job #2006869)
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 505
using namespace std;
ifstream si("car.in");
ofstream so("car.out");
int x[MAXN][MAXN];
int d[(1<<21)+5];
vector<int>q[2];
int sol,n,m;
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int xf,yf;
inline int cod(int i,int j,int dir)
{
return ((i<<9)+j+(dir<<18));
}
void decod(int c,int&i,int&j,int&dir)
{
j=c&511;
i=(c>>9)&511;
dir=c>>18;
}
bool expand(int st)
{
int i,j,dir;
int nst;
decod(st,i,j,dir);
nst=cod(i,j,(dir+7)%8);
if(d[nst]>d[st]+1)
{
d[nst]=d[st]+1;
q[d[nst]&1].push_back(nst);
}
nst=cod(i,j,(dir+1)%8);
if(d[nst]>d[st]+1)
{
d[nst]=d[st]+1;
q[d[nst]&1].push_back(nst);
}
i+=dx[dir];
j+=dy[dir];
if(i<1||j<1||i>n||j>m||x[i][j])
return false;
nst=cod(i,j,dir);
if(d[nst]>d[st])
{
d[nst]=d[st];
q[d[nst]&1].push_back(nst);
}
if(i==xf&&j==yf)
return true;
return false;
}
int main()
{
si>>n>>m;
int xs,ys;
si>>xs>>ys>>xf>>yf;
int st;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
si>>x[i][j];
for(int i=0;i<(1<<21)+5;++i)
d[i]=1<<30;
for(int i=0;i<8;++i)
{
st=cod(xs,ys,i);
q[0].push_back(st);
d[st]=0;
}
while(q[0].size()+q[1].size())
{
while(!q[sol&1].empty())
{
st=q[sol&1].back();
q[sol&1].pop_back();
if(expand(st))
{
so<<sol<<'\n';
return 0;
}
}
++sol;
}
so<<-1;
return 0;
}