Pagini recente » Cod sursa (job #2745334) | Cod sursa (job #577004) | Cod sursa (job #3135032) | Cod sursa (job #545990) | Cod sursa (job #2096556)
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
const int NMAX = 500;
const int VMAX = 1 + (1 << 21);
const int INF = 1 << 20;
const int DCD = 511;
class Coord {
public:
int x;
int y;
};
int dist[1 + VMAX];
int n, m, res;
int a[1 + NMAX][1 + NMAX];
vector < int > l[2];
short int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
short int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
Coord st, fn;
int code(int i, int j, int dir) {
int code = (i << 9) + j + (dir << 18);
return code;
}
void decode(int state, int &i, int &j, int &dir) {
j = state & DCD;
dir = state >> 18;
i = (state >> 9) & DCD;
}
bool ok(int x, int y) {
if(x < 1 || y < 1 || x > n || y > m || a[x][y] == 1)
return false;
else
return true;
}
bool expand(int state) {
int x, y, dir;
int cstate;
decode(state, x, y, dir);
cstate = code(x, y, (dir + 7) % 8);
if(dist[state] + 1 < dist[cstate]) {
dist[cstate] = dist[state] + 1;
l[dist[cstate] & 1].push_back(cstate);
}
cstate = code(x, y, (dir + 1) % 8);
if(dist[state] + 1 < dist[cstate]) {
dist[cstate] = dist[state] + 1;
l[dist[cstate] & 1].push_back(cstate);
}
x += dx[dir];if(dist[state] + 1 < dist[cstate]) {
dist[cstate] = dist[state] + 1;
l[dist[cstate] & 1].push_back(cstate);
}
y += dy[dir];
if(ok(x, y) == false) {
return false;
} else {
cstate = code(x, y, dir);
if(dist[state] < dist[cstate]) {
dist[cstate] = dist[state];
l[dist[cstate] & 1].push_back(cstate);
}
if(x == fn.x && y == fn.y)
return true;
else
return false;
}
}
int main()
{
in >> n >> m >> st.x >> st.y >> fn.x >> fn.y;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
in >> a[i][j];
}
}
for(int i = 0; i <= VMAX; i++)
dist[i] = INF;
for(int dir = 0; dir < 8; dir++) {
int state = code(st.x, st.y, dir);
l[0].push_back(state);
dist[state] = 0;
}
while(0 < l[0].size() + l[1].size()) {
while(l[res & 1]. size() != 0) {
int state = l[res & 1][l[res & 1].size() - 1];
l[res & 1].pop_back();
if(expand(state) == true) {
out << res << '\n';
exit(EXIT_SUCCESS);
}
}
res++;
}
out << "-1\n";
return 0;
}