Pagini recente » Cod sursa (job #3360231) | Cod sursa (job #3360154) | Cod sursa (job #3360230) | Cod sursa (job #3360131) | Cod sursa (job #3360194)
#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
#define inf 1e9
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMAX=501;
bool mat[NMAX][NMAX];
vector<pair<int,int>>direction={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};//transformam indexul directiei in (?cum se misca in matrice ?)
//prima e pt i si a doua j
int n,m;
int iStart,jStart,iEnd,jEnd;
struct stare{
int i,j;//poxitia curenta
short directie;//numerotam fiecare directie de la 1, la 7
/*(steluta ,wow)
\ 3|2/1
4___\|/___0
/|\
5/ | \7
6*/
int cost;//costul ca sa ajungem in starea curenta daca pornim de la (1,1)
bool operator<(const stare& other) const{
return cost>other.cost;
};
stare(int x,int y,int d,int c):i(x),j(y),directie(d),cost(c){};
};
int dist[NMAX][NMAX][8];//dist[i][j][d]= costul minim ca sa ajunga de la (0,0) la (i,j) cu directia d
void Disjakstra(){
deque<stare>pq;
for(int i=0;i<8;++i){
dist[iStart][jStart][i]=0;
pq.push_back(stare(iStart,jStart,i,0));
}
while (!pq.empty())
{
stare crt=pq.front();
pq.pop_front();
int dir1=(crt.directie+1)%8;
int dir2=(crt.directie-1+8)%8;//putem merge in orice sens
int costCrt=crt.cost+1;//are cost unu
if(dist[crt.i][crt.j][dir1]>costCrt){
dist[crt.i][crt.j][dir1]=costCrt;
stare newStare=crt;
newStare.directie=dir1;
newStare.cost=costCrt;
pq.push_back(newStare);//am vrea sa luam mai intai starile "ieftine"
//(adica sa mergem in aceasi directie pe care o avem acum cu cost 0)
//asa ca dam push back
}
if(dist[crt.i][crt.j][dir2]>costCrt){//facem fix acelasi lucru ca la dir 1
dist[crt.i][crt.j][dir2]=costCrt;
stare newStare=crt;
newStare.directie=dir2;
newStare.cost=costCrt;
pq.push_back(newStare);
}
int dir=crt.directie;
int newi=crt.i+direction[dir].first;
int newj=crt.j+direction[dir].second;
if(newi>=0 && newi<n && newj>=0 && newj<m && mat[newi][newj]==0 && mat[newi][newj]==0 && crt.cost<dist[newi][newj][dir]){
dist[newi][newj][dir]=crt.cost;
stare newStare=stare(newi,newj,crt.directie,crt.cost);
pq.push_front(newStare);
}
}
}
int getAnswer(){
int rez=inf;
for(int i=0;i<8;++i){
rez=min(rez,dist[iEnd][jEnd][i]);
}
if(rez==inf){
rez=-1;//da ,asta e o cerinta :)
}
return rez;
}
void setup(){
for(int i=0;i<NMAX;++i){
for(int j=0;j<NMAX;++j){
for(int k=0;k<8;++k){
dist[i][j][k]=inf;
}
}
}
}
void read(){
fin>>n>>m;
fin>>iStart>>jStart>>iEnd>>jEnd;
iStart--;
jStart--;
iEnd--;
jEnd--;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
fin>>mat[i][j];
}
}
}
int main(){
setup();
read();
Disjakstra();
fout<<getAnswer();
return 0;
}
//(^..^)