Pagini recente » Cod sursa (job #3257106) | Cod sursa (job #3288832) | Cod sursa (job #3290362) | Rating Vlad-Alexandru Onu (vladinski.on) | Cod sursa (job #3282712)
#include <bits/stdc++.h>
using namespace std;
ifstream f("car.in");
#define cin f
const int NMAX=505, INF=1e9;
bitset<NMAX> a[NMAX];
int n, m,sti, stj, fni, fnj, dir, x,y;
//de la diagonala dreapta sus
int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy[8] = {1, 1, 1, 0, -1, -1, -1, 0};
vector<vector<vector<int>>> d;
deque<tuple<int,int,int>> dq;
void bfs()
{
int rtdir;
d.assign(8,vector<vector<int>>(n+1,vector<int>(m+1, INF)));
for(int i=0; i<8; i++)
{
d[i][sti][stj]=0;
dq.push_back({i, sti, stj});
}
while(!dq.empty())
{
tie(dir, x, y)=dq.front();
int px = x+dx[dir];
int py = y+dy[dir];
dq.pop_front();
//la final d[dir][x][y]<d[dir][px][py] este pentru a verifica daca am gasit un
//drum deja mai scurt decat cel pe care il avem acum
if(px>=1 && px<=n && py>=1 && py<=m && !a[px][py] && d[dir][x][y]<d[dir][px][py])
{
d[dir][px][py]=d[dir][x][y];
dq.push_front({dir, px, py});
}
for(int k=-1; k<=1; k+=2)
{
rtdir =(dir+k+8)%8;
if(d[dir][x][y]+1<d[rtdir][x][y])
{
d[rtdir][x][y]=d[dir][x][y]+1;
dq.push_back({rtdir, x, y});
}
}
}
}
int main()
{
//in dq avem distanta, coordonate
cin >> n >> m;
cin >> sti >> stj >> fni >> fnj;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cin >> x;
a[i][j]=x;
}
}
bfs();
int t=INF;
for(int i=0; i<8; i++)
if(d[i][fni][fnj]<t)
t=d[i][fni][fnj];
if(t==INF)
cout << -1;
else cout << t;
}