Pagini recente » Cod sursa (job #2039142) | Cod sursa (job #1329950) | Cod sursa (job #501867) | Cod sursa (job #19220) | Cod sursa (job #2285120)
#include <iostream>
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;
const int nmax=500;
int n,m,i,li,lf,ci,cf,costul,cost,j;
int d1[]={-1,-1,-1,0,1,1,1,0};
int d2[]={-1,0,1,1,1,0,-1,-1};
bitset<nmax+5> a[8][nmax+5];
struct type
{
int l,c,d;
}el;
vector<type> v[4*nmax*nmax+5];
bool mat[nmax+5][nmax+5],found;
void dfs(int x,int y,int dir)
{
if(x==0||y==0||x==n+1||y==m+1||found) return;
if(mat[x][y]==1) return;
el.l=x;
el.c=y;
a[dir][x][y]=1;
if(x==lf&&y==cf)
{
costul=cost;
found=1;
return;
}
if(dir>=1) el.d=dir-1;
else el.d=7;
if(a[el.d][x][y]==0)
{
v[cost+1].push_back(el);
}
if(dir<7) el.d=dir+1;
else el.d=0;
if(a[el.d][x][y]==0)
{
v[cost+1].push_back(el);
}
if(a[dir][x+d1[dir]][y+d2[dir]]==0)
dfs(x+d1[dir],y+d2[dir],dir);
}
int main()
{
ifstream f("car.in");
ofstream g("car.out");
f>>n>>m;
f>>li>>ci>>lf>>cf;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>mat[i][j];
//DIRECTII
//0 ST sus
//1 sus
//2 DR sus
//3 DR
//4 DR jos
//5 jos
//6 ST jos
//7 ST
el.l=li;el.c=ci;
for(i=0;i<8;i++)
{
a[i][li][ci]=1;
el.d=i;
v[1].push_back(el);
}
if(mat[li][ci]==1||mat[lf][cf]==1) found=1;
for(cost=1;found==0;cost++)
{
if(cost>4*n) found=1;
for(j=0;j<v[cost].size();j++)
{
dfs(v[cost][j].l,v[cost][j].c,v[cost][j].d);
}
}
g<<costul-1;
return 0;
}