Pagini recente » Cod sursa (job #2262638) | Cod sursa (job #2641041) | Cod sursa (job #770776) | Cod sursa (job #1621051) | Cod sursa (job #2030047)
#include <bits/stdc++.h>
using namespace std;
const int maxN=505;
const int INF=0x3f3f3f3f;
class inParser
{
public:
inParser(){};
inParser(const char *file_name)
{
input_file=fopen(file_name,"r");
cursor=0;
fread(buffer,SIZE,1,input_file);
}
inline inParser &operator >>(int &n)
{
while(buffer[cursor]<'0' || buffer[cursor]>'9')
advance();
n=0;
while('0'<=buffer[cursor] && buffer[cursor]<='9'){
n=n*10+buffer[cursor]-'0';
advance();
}
return *this;
}
private:
FILE *input_file;
static const int SIZE=1<<15;
int cursor;
char buffer[SIZE];
inline void advance()
{
cursor++;
if(cursor==SIZE){
cursor=0;
fread(buffer,SIZE,1,input_file);
}
}
};
const int dx[]={-1,-1,-1,0,1,1,1,0};
const int dy[]={-1,0,1,1,1,0,-1,-1};
int a[maxN][maxN];
int dist[maxN][maxN][8];
int n,m,xst,yst,xfn,yfn;
deque<pair<pair<int,int>,int> >deq;
int main()
{
inParser f("car.in");
freopen("car.out","w",stdout);
f>>n>>m;
f>>xst>>yst>>xfn>>yfn;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f>>a[i][j];
memset(dist,INF,sizeof(dist));
for(int i=0;i<=n+1;i++)
a[i][0]=a[i][m+1]=1;
for(int i=0;i<=m+1;i++)
a[0][i]=a[n+1][i]=1;
for(int i=0;i<8;i++){
dist[xst][yst][i]=0;
deq.push_front({{xst,yst},i});
}
while(!deq.empty())
{
int x=deq.front().first.first;
int y=deq.front().first.second;
int dir=deq.front().second;
deq.pop_front();
if(x==xfn && y==yfn){
printf("%d",dist[x][y][dir]);
return 0;
}
int newdir=(dir+7)%8;
if(!a[x][y] && dist[x][y][newdir]>dist[x][y][dir]+1){
dist[x][y][newdir]=dist[x][y][dir]+1;
deq.push_back({{x,y},newdir});
}
newdir=(dir+1)%8;
if(!a[x][y] && dist[x][y][newdir]>dist[x][y][dir]+1){
dist[x][y][newdir]=dist[x][y][dir]+1;
deq.push_back({{x,y},newdir});
}
newdir=dir;
if(!a[x+dx[dir]][y+dy[dir]] && dist[x+dx[dir]][y+dy[dir]][newdir]>dist[x][y][dir]){
dist[x+dx[dir]][y+dy[dir]][newdir]=dist[x][y][dir];
deq.push_front({{x+dx[dir],y+dy[dir]},newdir});
}
}
printf("-1");
return 0;
}