Pagini recente » Cod sursa (job #1035139) | Cod sursa (job #1549269) | Cod sursa (job #2173407) | Cod sursa (job #1286845) | Cod sursa (job #1440360)
#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 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)
G[((i-1)*M+j)*8-8+dir].push_back(make_pair(((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)
G[((i-1)*M+j)*8-8+dir].push_back(make_pair(((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)
G[((i-1)*M+j)*8-8+dir].push_back(make_pair(((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(500*500*2+1);
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++)
{
if(!Bucket[cost].empty())
{
list<int> :: iterator it;
for(it=Bucket[cost].begin();it!=Bucket[cost].end();it++)
{
int node=*it;
for(int i=0;i<G[node].size();i++)
{
int neighb=G[node][i].first,cost=G[node][i].second;
if(D[neighb]>D[node]+cost)
{
if(D[neighb]!=INF)
Bucket[D[neighb]].remove(neighb);
D[neighb]=D[node]+cost;
Bucket[D[neighb]].push_back(neighb);
}
}
}
}
}
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();
buildG();
Dijkstra();
return 0;
}