Pagini recente » Cod sursa (job #3265138) | Cod sursa (job #2704226) | Cod sursa (job #3163037) | Cod sursa (job #2033681) | Cod sursa (job #1500588)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMax = 505;
const int INF = 1e9;
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
bool v[NMax][NMax];
int val[NMax][NMax];
deque < int > Dir, Qx, Qy;
inline void Solve(const int &x, const int &y, const int &a, const int &value){
int nx, ny;
nx = x + dx[a];
ny = y + dy[a];
if(!v[nx][ny] && val[x][y] + value < val[nx][ny]){
val[nx][ny] = val[x][y] + value;
Qx.push_back(nx);
Qy.push_back(ny);
Dir.push_back(a);
}
}
inline void Lee(){
int x, y, D, lo, hi;
while(!Qx.empty()){
x = Qx.front(); Qx.pop_front();
y = Qy.front(); Qy.pop_front();
D = Dir.front(); Dir.pop_front();
lo = hi = D;
for(int i = 0; i < 5; i++){
Solve(x, y, lo, i);
if(lo != hi){
Solve(x, y, hi, i);
}
lo--;
if(lo < 0) lo = 7;
hi++;
if(hi > 7) hi = 0;
}
}
}
int main(){
int n, m, x, y, X, Y;
fin >> n >> m >> x >> y >> X >> Y;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
fin >> v[i][j];
}
}
for(int i = 0; i <= n + 1; i++){
v[i][0] = v[i][m + 1] = 1;
}
for(int i = 0; i <= m + 1; i++){
v[0][i] = v[n + 1][i] = 1;
}
for(int i = 0; i < 8; i++){
Qx.push_back(x);
Qy.push_back(y);
Dir.push_back(i);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
val[i][j] = INF;
}
}
val[x][y] = 0;
Lee();
fout << val[X][Y];
return 0;
}