Cod sursa(job #3253752)

Utilizator luc3lexaAlexandrescu Luca luc3lexa Data 4 noiembrie 2024 17:56:55
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#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;
}