Cod sursa(job #1064912)

Utilizator stefanzzzStefan Popa stefanzzz Data 22 decembrie 2013 15:02:30
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <fstream>
#include <set>
#define MAXN 505
#define INF 2000000000
using namespace std;
ifstream f("car.in");
ofstream g("car.out");

struct nod{
    int x,y,dir;};

int n,m,sx,sy,fx,fy,dp[MAXN][MAXN][8],dirx[8]={0,1,1,1,0,-1,-1,-1} ,diry[8]={-1,-1,0,1,1,1,0,-1},t1,t2,sol;
char s[MAXN];
bool a[MAXN][MAXN];
nod aux,aux2;

struct Comp{
    bool operator()(nod p,nod q){
        if(dp[p.x][p.y][p.dir]==dp[q.x][q.y][q.dir]){
            if(p.x==q.x){
                if(p.y==q.y)
                    return p.dir<q.dir;
                return p.y<q.y;}
            return p.x<q.x;}
        return dp[p.x][p.y][p.dir]<dp[q.x][q.y][q.dir];}};

set<nod,Comp> v;
set<nod,Comp>::iterator it;

void citire();
int costcurba(int d1,int d2);

int main()
{
    int i,j,k;
    citire();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            for(k=0;k<8;k++)
                dp[i][j][k]=INF;
    aux.x=sx;aux.y=sy;
    for(i=0;i<8;i++){
        dp[sx][sy][i]=0;
        aux.dir=i;
        v.insert(aux);}
    while(!v.empty()){
        aux=(*v.begin());
        v.erase(v.begin());
        if(aux.x==fx&&aux.y==fy)
            break;
        for(i=0;i<8;i++){
            if(a[aux.x+dirx[i]][aux.y+diry[i]])
                continue;
            t1=dp[aux.x+dirx[i]][aux.y+diry[i]][i];
            t2=dp[aux.x][aux.y][aux.dir]+costcurba(aux.dir,i);
            if(t1>t2){
                aux2.x=aux.x+dirx[i];
                aux2.y=aux.y+diry[i];
                aux2.dir=i;
                if(t1<INF)
                    v.erase(aux2);
                dp[aux2.x][aux2.y][aux2.dir]=t2;
                v.insert(aux2);}}}
    sol=INF;
    for(i=0;i<8;i++)
        if(dp[fx][fy][i]<sol)
            sol=dp[fx][fy][i];
    if(sol==INF){
        g<<"-1\n";
        return 0;}
    g<<sol<<'\n';
    f.close();
    g.close();
    return 0;
}

void citire(){
    int i,j;
    f>>n>>m>>sx>>sy>>fx>>fy;
    f.getline(s,MAXN,'\n');
    for(i=1;i<=n;i++){
        f.getline(s+2,MAXN,'\n');
        for(j=1;j<=m;j++)
            a[i][j]=s[2*j]-'0';
        a[i][0]=a[i][m+1]=1;}
    for(i=0;i<=m+1;i++)
        a[0][i]=a[n+1][i]=1;}


int costcurba(int d1,int d2){
    int cst;
    cst=d1-d2;
    if(cst<0)
        cst=d2-d1;
    if(cst>4)
        cst=8-cst;
    return cst;}