Pagini recente » Cod sursa (job #3360190) | Cod sursa (job #3360241) | Cod sursa (job #3360184) | Cod sursa (job #3360200) | Cod sursa (job #3360193)
#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;
int costCrt=crt.cost+1;
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);
}
if(dist[crt.i][crt.j][dir2]>costCrt){
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;
}
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;
}