Pagini recente » Cod sursa (job #1860599) | Cod sursa (job #2430492) | Cod sursa (job #1860459) | Cod sursa (job #2779386) | Cod sursa (job #1043094)
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int knmax = 2008008;
const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
class node{
public:
int x, y, d, t;
node(){};
node(int T){
t = T;
d = T % 8;
y = T / 8 % 501;
x = T / 8 / 501;
}
node(int x1, int y1, int d1){
x = x1;
y = y1;
d = d1;
t = x * 8 * 501 + y * 8 + d;
}
};
node down(node p){
return node(p.x, p.y, (p.d + 7) % 8);
}
node up(node p){
return node(p.x, p.y, (p.d + 1) % 8);
}
node next(node p){
return node(p.x + dx[p.d], p.y + dy[p.d], p.d);
}
int startx, starty, destx, desty;
int n, m, dist[2008008], mat[505][505];
inline int valid(node &x){
if(x.x > n || x.x < 1 || x.y > m || x.y < 1 || dist[x.t] != -1)
return 0;
if(mat[x.x][x.y] == 1)
return 0;
return 1;
}
int main(){
ifstream in("car.in");
ofstream out("car.out");
memset(dist, -1, sizeof(dist));
in >> n >> m;
in >> startx >> starty >> destx >> desty;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
in >> mat[i][j];
vector<node> q1, q2;
for(int i = 0; i < 8; ++i){
node t(startx, starty, i);
q2.push_back(t);
dist[t.t] = 0;
}
while(!q2.empty()){
q1 = q2;
q2.clear();
for(int i = 0; i < q1.size(); ++i){
node nxt = next(q1[i]);
if(valid(nxt)){
dist[nxt.t] = dist[q1[i].t];
q1.push_back(nxt);
}
}
for(int i = 0; i < q1.size(); ++i){
node n1 = up(q1[i]), n2 = down(q1[i]);
if(valid(n1)){
dist[n1.t] = dist[q1[i].t] + 1;
q2.push_back(n1);
}
if(valid(n2)){
dist[n2.t] = dist[q1[i].t] + 1;
q2.push_back(n2);
}
}
}
int ans = 2e9;
for(int i = 0; i < 8; ++i){
node t(destx, desty, i);
ans = min(ans, dist[t.t]);
}
out << ans;
return 0;
}