Cod sursa(job #1501062)

Utilizator ciocan_catalinCiocan Catalin - Iulian ciocan_catalin Data 12 octombrie 2015 23:04:32
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int n,m,si,sj,fi,fj;
int a[505][505],b[505][505];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
int suma[10][10];
//N,NE,E,SE,S,SV,V,NV


struct coord
{
    int x,y,d;
};

queue<coord> Q;
coord w;

void Read()
{
    int i,j;
    fin>>n>>m>>si>>sj>>fi>>fj;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++) fin>>a[i][j];
}

bool OK(int i, int j)
{
    if(i<1 || j<1 || i>n || j>m) return false;
    return true;
}

void SUM()
{
    int i,j;
    for(i=0;i<=7;i++)
        for(j=0;j<=7;j++) suma[i][j] = min(min(abs(j-i),abs(i-j)),min(abs(i+8-j),abs(j+8-i)));

}


void Lee()
{
    int i,j,in,jn,dir,directie,sum;
    coord w1,w2;
    i = si;
    j = fi;
    for(dir=0;dir<8;dir++)
    {
        in = i+dx[dir];
        jn = j+dy[dir];
        if(OK(in,jn) && a[in][jn]==0)
        {
            w.x = in;
            w.y = jn;
            w.d = dir;
            Q.push(w);
        }
    }
    while(!Q.empty())
    {
        w1 = Q.front();
        Q.pop();
         for(dir=0;dir<8;dir++)
        {
            in = w1.x+dx[dir];
            jn = w1.y+dy[dir];
            directie = w1.d;
            sum = suma[dir][directie];
        if(OK(in,jn) && a[in][jn]==0)
        {
            if(b[in][jn]==0 ||b[in][jn]>b[w1.x][w1.y]+sum)
            {
            w2.x = in;
            w2.y = jn;
            w2.d = dir;
            Q.push(w2);
            b[in][jn] = b[w1.x][w1.y]+sum;
            }
        }

        }

    }
}



int main()
{
    Read();
    SUM();
    Lee();
    if(si==fi && sj==fj) fout<<"0\n";
    else if(b[fi][fj]==0) fout<<"-1";
    else fout<<b[fi][fj]<<"\n";
    fout.close();
    return 0;
}