Pagini recente » Cod sursa (job #904003) | Cod sursa (job #2928803) | Cod sursa (job #2127967) | Cod sursa (job #2128265) | Cod sursa (job #1440496)
#include <fstream>
#include <vector>
#include <list>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int N,M;
int X1,Y1,X2,Y2;
const int INF = 0x3f3f3f3f;
bool Matrix[505][505];
vector < list<int> > Bucket;
vector < pair<int,int> > G[505*505*8];
int D[505*505*8];
int dx[]={1,1,0,-1,-1,-1,0,1};
int dy[]={0,1,1,1,0,-1,-1,-1};
void Read()
{
f>>N>>M>>X1>>Y1>>X2>>Y2;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
f>>Matrix[i][j];
}
inline bool Valid(int i,int j)
{
return i>0 && j>0 && i<=N && j<=M && Matrix[i][j]==0;
}
void Change(int node,int neighb,int cost)
{
if(D[neighb]>D[node]+cost)
{
if(D[neighb]!=INF)
Bucket[D[neighb]%3].remove(neighb);
D[neighb]=D[node]+cost;
Bucket[D[neighb]%3].push_back(neighb);
}
}
void buildEdge(int i,int j,int dir)
{
int c=0,k=dir;
for(;c<=2;c++)
{
if(c==0)
{
if(Valid(i+dx[k],j+dy[k])==1)
Change(((i-1)*M+j)*8-8+dir,((i+dx[k]-1)*M+j+dy[k])*8-8+k,0);
continue;
}
int x=k+c;
if(x>=8)
x-=8;
if(Valid(i+dx[x],j+dy[x])==1)
Change(((i-1)*M+j)*8-8+dir,((i+dx[x]-1)*M+j+dy[x])*8-8+x,c);
x=k-c;
if(x<0)
x+=8;
if(Valid(i+dx[x],j+dy[x])==1)
Change(((i-1)*M+j)*8-8+dir,((i+dx[x]-1)*M+j+dy[x])*8-8+x,c);
}
}
void buildG()
{
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
{
if(Matrix[i][j]==0)
{
for(int dir=0;dir<8;dir++)
buildEdge(i,j,dir);
}
}
}
void Dijkstra()
{
for(int i=0;i<=N*M*8;i++)
D[i]=INF;
Bucket.resize(3);
for(int k=0;k<8;k++)
Bucket[0].push_back(((X1-1)*M+Y1)*8+k-8),D[((X1-1)*M+Y1)*8+k-8]=0;
for(int cost=0;cost<=500*500*2;cost++)
{
int x=cost%3;
if(!Bucket[x].empty())
{
list<int> :: iterator it;
for(it=Bucket[x].begin();it!=Bucket[x].end();it++)
{
int node=*it;
int dir = node % 8;
node /= 8;
int j = (node % M) + 1;
int i = (node / M) + 1;
buildEdge(i,j,dir);
}
}
}
int Min=INF;
for(int i=0;i<8;i++)
Min=min(Min,D[((X2-1)*M+Y2)*8+i-8]);
if(Min==INF)
Min=-1;
g<<Min<<"\n";
}
int main()
{
Read();
Dijkstra();
return 0;
}