Pagini recente » Cod sursa (job #1163162) | Cod sursa (job #1904082) | Cod sursa (job #1898403) | Cod sursa (job #3245944) | Cod sursa (job #1657427)
#include <algorithm>
#include <bitset>
#include <cmath>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string.h>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> ppiii;
ifstream fin ("car.in");
ofstream fout ("car.out");
const int INF = 0x3f3f3f3f;
const int Nmax = 555;
int N, M, si, sj, fi, fj, ni, nj, ndir, lvl = 0;
int d[Nmax][Nmax][8];
char vis[Nmax][Nmax][8];
char bd[Nmax][Nmax];
queue<ppiii> Q[2];
int di[8]={-1,-1,0,1,1,1,0,-1};
int dj[8]={0,1,1,1,0,-1,-1,-1};
inline int min(int x, int y) { return x < y ? x : y;}
inline int max(int x, int y) { return x > y ? x : y;}
inline int abs(int x) { return x > 0 ? x : -x; }
void pp() {
cout << string(80, '=') << endl;
for(int i = 0; i < N; ++i)
for(int j = 0; j < M; ++j) {
cout << '('<< i << "x" << j << "):[";
cout << d[i][j][0];
for (int dir = 1; dir < 8; ++dir)
cout << ',' << d[i][j][dir];
cout << ']';
cout << (j == M-1 ? '\n' : '#');
}
}
int main() {
fin >> N >> M;
fin >> si >> sj >> fi >> fj;
--si, --sj, --fi, --fj;
memset(d, -1, sizeof(d));
for(int i = 0; i < N; ++i)
for(int j = 0; j < M; ++j) {
fin >> bd[i][j];
}
for(int dir = 0; dir < 8; ++dir) {
d[si][sj][dir] = 0;
Q[lvl].push({{si, sj}, dir});
}
bool done = 0;
while(!done) {
while(!Q[lvl].empty()) {
ppiii P = Q[lvl].front(); Q[lvl].pop();
pii pos = P.first;
int dir = P.second;
vis[pos.first][pos.second][dir] = 1;
if (pos.first == fi && pos.second == fj) {
done = 1;
break;
}
// don't change direction
ni = pos.first + di[dir];
nj = pos.second + dj[dir];
while(ni >= 0 && ni < N && nj >= 0 && nj < M && bd[ni][nj] == '0' && vis[ni][nj][dir] == 0) {
if (d[ni][nj][dir] == -1 || d[ni][nj][dir] > d[pos.first][pos.second][dir]) {
d[ni][nj][dir] = d[pos.first][pos.second][dir];
Q[lvl].push({{ni, nj}, dir});
}
ni += di[dir];
nj += dj[dir];
}
// change direction
for(int i = -1; i < 2; i += 2) {
ndir = (dir+i+8)&7;
ni = pos.first;
nj = pos.second;
if (vis[ni][nj][ndir])
continue;
if (d[ni][nj][ndir] == -1 || d[ni][nj][ndir] > d[pos.first][pos.second][dir] + 1) {
d[ni][nj][ndir] = d[pos.first][pos.second][dir] + 1;
Q[1-lvl].push({{ni, nj}, ndir});
}
}
}
lvl = 1-lvl;
if (Q[lvl].empty())
done = 1;
}
//pp();
int ans = INF;
for(int dir = 0; dir < 8; ++dir) {
if (d[fi][fj][dir] == -1)
continue;
ans = min(ans, d[fi][fj][dir]);
}
fout << (ans == INF ? -1 : ans) << endl;
return 0;
}