Pagini recente » Cod sursa (job #941386) | Cod sursa (job #129119) | Cod sursa (job #2185750) | Cod sursa (job #2457133) | Cod sursa (job #828409)
Cod sursa(job #828409)
#include <fstream>
#include <queue>
using namespace std;
const char InFile[]="car.in";
const char OutFile[]="car.out";
const int MaxN=503;
const int dx[]={1, 1, 0, -1, -1, -1, 0, 1};
const int dy[]={0, 1, 1, 1, 0, -1, -1, -1};
const int DIR=8;
const int INF=1<<30;
ifstream fin(InFile);
ofstream fout(OutFile);
struct Node
{
Node(int x=0, int y=0, int dir=0):x(x),y(y),dir(dir){}
inline void Move()
{
x+=dx[dir];
y+=dy[dir];
}
inline void RotateCW()
{
dir+=7;
dir%=DIR;
}
inline void RotateCCW()
{
++dir;
dir%=DIR;
}
int x,y,dir;
};
int N,M,A[MaxN][MaxN],sol,D[MaxN][MaxN][DIR],stx,sty,sfx,sfy,curr;
char expanded[MaxN][MaxN][DIR];
queue<Node> Q[2];
inline void Update(const Node &from, const Node &to, const int &cost)
{
if(!A[to.x][to.y] && D[to.x][to.y][to.dir]>D[from.x][from.y][from.dir]+cost)
{
D[to.x][to.y][to.dir]=D[from.x][from.y][from.dir]+cost;
Q[curr^cost].push(to);
}
}
int main()
{
fin>>N>>M;
fin>>stx>>sty>>sfx>>sfy;
for(register int i=1;i<=N;++i)
{
for(register int j=1;j<=M;++j)
{
fin>>A[i][j];
}
}
fin.close();
for(register int i=0;i<=N+1;++i)
{
A[i][0]=A[i][M+1]=1;
}
for(register int j=0;j<=M+1;++j)
{
A[0][j]=A[N+1][j]=1;
}
for(register int i=1;i<=N;++i)
{
for(register int j=1;j<=N;++j)
{
for(register int d=0;d<DIR;++d)
{
D[i][j][d]=INF;
}
}
}
for(register int d=0;d<DIR;++d)
{
D[stx][sty][d]=0;
Q[0].push(Node(stx,sty,d));
}
curr=0;
while(!Q[curr].empty())
{
while(!Q[curr].empty())
{
Node nod=Q[curr].front();
Q[curr].pop();
if(expanded[nod.x][nod.y][nod.dir])
{
continue;
}
if(nod.x==sfx && nod.y==sfy)
{
sol=D[sfx][sfy][nod.dir];
goto afis;
}
Node to=nod; to.Move();
Update(nod,to,0);
to=nod; to.RotateCW();
Update(nod,to,1);
to=nod; to.RotateCCW();
Update(nod,to,1);
}
curr^=1;
}
afis:
fout<<sol;
fout.close();
return 0;
}