Pagini recente » Cod sursa (job #1215088) | Cod sursa (job #1099389) | Cod sursa (job #1727665) | Cod sursa (job #3146765) | Cod sursa (job #3253752)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int nmax = 510;
const int directions = 8;
const int inf = 1e9;
const int di[] = {-1,-1,-1,0,1,1,1,0};
const int dj[] = {-1,0,1,1,1,0,-1,-1};
bitset<nmax> mat[nmax];
bitset<nmax> visited[directions+1][nmax];
vector<vector<vector<int>>> dp(directions,vector<vector<int>> (nmax,vector<int> (nmax,inf)));
int n,m,i_start,j_start,i_end,j_end;
vector<queue<pair<int,pair<int,int>>>> q(3);
inline int inmat(int i,int j){
if(i >= 1 && i <=n && j >=1 && j <=m){
return 1;
};
return 0;
}
void read_input(){
fin >> n >> m;
fin >> i_start >> j_start >> i_end >> j_end;
int aux;
for(int i = 1; i <=n; i++){
for(int j = 1; j <=m; j++){
fin >> aux;
mat[i][j] = aux;
}
}
}
void dijkstra(int i_start,int j_start){
for(int i = 0; i < directions; i++){
dp[i][i_start][j_start] = 0;
q[0].push(make_pair(i,make_pair(i_start,j_start)));
};
int number_elements = directions,index_queue = 0;
int next_direction,next_i,next_j;
int curr_direction,curr_i,curr_j;
while(number_elements != 0){
while(q[index_queue].empty()){
index_queue = (index_queue+1)%3;
};
curr_direction = q[index_queue].front().first;
curr_i = q[index_queue].front().second.first;
curr_j = q[index_queue].front().second.second;
q[index_queue].pop();
number_elements--;
if(!visited[curr_direction][curr_i][curr_j]){
for(int k = -2; k < 0; k++){
next_direction = (curr_direction + k + directions)%directions;
next_i = curr_i + di[next_direction];
next_j = curr_j + dj[next_direction];
if(inmat(next_i,next_j) && !visited[next_direction][next_i][next_j] &&
!mat[next_i][next_j] && dp[next_direction][next_i][next_j] > dp[curr_direction][curr_i][curr_j] - k){
dp[next_direction][next_i][next_j] = dp[curr_direction][curr_i][curr_j] - k;
number_elements++;
q[(index_queue - k)%3].push(make_pair(next_direction,make_pair(next_i,next_j)));
}
}
for(int k = 0; k <= 2; k++){
next_direction = (curr_direction + k)%directions;
next_i = curr_i + di[next_direction];
next_j = curr_j + dj[next_direction];
if(inmat(next_i,next_j) && !visited[next_direction][next_i][next_j] &&
!mat[next_i][next_j] && dp[next_direction][next_i][next_j] > dp[curr_direction][curr_i][curr_j] + k){
dp[next_direction][next_i][next_j] = dp[curr_direction][curr_i][curr_j] + k;
number_elements++;
q[(index_queue + k)%3].push(make_pair(next_direction,make_pair(next_i,next_j)));
}
}
visited[curr_direction][curr_i][curr_j] = 1;
}
}
}
int main(){
read_input();
dijkstra(i_start,j_start);
int ans = inf;
for(int i = 0; i < directions; i++){
ans = min(ans,dp[i][i_end][j_end]);
};
fout << (ans == inf ? -1 : ans);
return 0;
}