Pagini recente » Cod sursa (job #1134728) | Cod sursa (job #751931) | Cod sursa (job #3320917) | Cod sursa (job #3321081) | Cod sursa (job #3307079)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMAX=500, directions=8, inf=1e9;
int mat[NMAX+5][NMAX+5];
vector<vector<vector<int>>> dist(directions, vector<vector<int> >(NMAX+5, vector<int>(NMAX+5, inf)));
int xs, ys, xf, yf;
const int dx[]={-1,-1,-1,0,1,1,1,0};
const int dy[]={-1,0,1,1,1,0,-1,-1};
int n, m;
bool inmat(int x, int y){
return x>=1 and x<=n and y>=1 and y<=m;
}
void dial(){
queue<tuple<int,int,int> > q[3];
int cnt=directions, cur=0;
for(int i=0;i<directions;i++){
q[cur].push(tie(xs,ys,i));
dist[i][xs][ys]=0;
}
while(cnt){
while(q[cur].empty()){
cur=(cur+1)%3;
}
int x, y, direction;
tie(x, y, direction)=q[cur].front();
q[cur].pop();
cnt--;
for(int k=-2;k<=2;k++){
int nx, ny, ndirection;
ndirection=(direction+k+directions)%directions;
nx=x+dx[ndirection];
ny=y+dy[ndirection];
if(inmat(nx,ny) and mat[nx][ny]==0){
if(dist[ndirection][nx][ny]>dist[direction][x][y]+abs(k)){
dist[ndirection][nx][ny]=dist[direction][x][y]+abs(k);
q[(cur+abs(k))%3].push({nx,ny,ndirection});
cnt++;
}
}
}
}
}
int main(){
fin>>n>>m>>xs>>ys>>xf>>yf;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
fin>>mat[i][j];
}
}
dial();
int ans=inf;
for(int i=0;i<directions;i++){
ans=min(ans, dist[i][xf][yf]);
}
if(ans!=inf){
fout<<ans;
}else{
fout<<-1;
}
}