Pagini recente » Cod sursa (job #998750) | Cod sursa (job #178527) | Cod sursa (job #2548418) | Cod sursa (job #562712) | Cod sursa (job #969062)
Cod sursa(job #969062)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <ctime>
#include <utility>
#include <string.h>
using namespace std;
ifstream cin("car.in");
ofstream cout("car.out");
const int MAXN = 505,
oo = ((1<<31)-1),
dx[8]={ 1, 1, 0, -1, -1, -1, 0, 1 },
dy[8]={ 0, 1, 1, 1, 0, -1, -1, -1 };
struct mpair{
int x, y, dir;
mpair(int _x, int _y, int _dir){
x = _x;
y = _y ;
dir = _dir;
}
};
queue <mpair> Q[2];
int a[MAXN][MAXN], d[MAXN][MAXN][8];
int n, m;
inline bool isokay(int i, int j)
{
return (i >= 1 && j >= 1 && i <= n && j <= m && !a[i][j]);
}
int main()
{
int stx, sty, fnx, fny;
cin >> n >> m;
cin >> stx >> sty >> fnx >> fny;
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j)
{
cin >> a[i][j];
for(int k = 0 ; k < 8 ; ++ k)
d[i][j][k] = oo;
}
cin.close();
for(int i = 0 ; i < 8 ; ++ i)
{
d[stx][sty][i] = 0;
Q[0].push(mpair(stx, sty, i));
}
int c = 0 ;
while(true)
{
int i;
for(i = 0 ; Q[i].empty() ; ++i);
if(i >= 2)
break;
int x = Q[i].front().x;
int y = Q[i].front().y;
int dir = Q[i].front().dir;
Q[i].pop();
// "tot inainte"
int xnou = x + dx[dir];
int ynou = y + dy[dir];
if( isokay(xnou, ynou) && d[xnou][ynou][dir] > d[x][y][dir])
{
d[xnou][ynou][dir] = d[x][y][dir];
Q[0].push(mpair(xnou, ynou, dir));
}
if( d[x][y][(dir+8+1)&7] > d[x][y][dir] + 1)
{
d[x][y][(dir+8+1)&7] = d[x][y][dir] + 1;
Q[1].push(mpair(x, y, (dir+8+1)&7));
}
if( d[x][y][(dir+8-1)&7] > d[x][y][dir] + 1)
{
d[x][y][(dir+8-1)&7] = d[x][y][dir] + 1;
Q[1].push(mpair(x, y, (dir+8-1)&7));
}
}
int sol = oo;
for(int i = 0 ; i < 8 ; ++ i)
sol = min(sol, d[fnx][fny][i]);
cout << ( sol == oo ? -1 : sol) << "\n";
cout.close();
return 0;
}