Cod sursa(job #1501286)

Utilizator CraiuAndrei Craiu Craiu Data 13 octombrie 2015 10:38:13
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;

int n, m, xs, ys, xf, yf;
int a[505][505], b[505][505];
int dx[] = {0, 1, 1,  1,  0, -1, -1, -1};
int dy[] = {1, 1, 0, -1, -1, -1,  0,  1};

struct Coord
{
    int x, y, cost;
};

queue <Coord> q;

bool ok(int i, int j)
{
    if(i > 0 && j > 0 && i <= n && j <= m)  return 1;
    return 0;
}

void Read()
{
    int i, j;
    ifstream fin("car.in");
    fin >> n >> m;
    fin >> xs >> ys >> xf >> yf;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            fin >> a[i][j];
    fin.close();
}


inline void Lee(int xs, int ys)
{
    int i, j, k, x, y;
    Coord w, w1;
    w.x = xs;
    w.y = ys;
    w.cost = 0;
    q.push(w);
    b[xs][ys] = 0;
    while(!q.empty())
    {
        w = q.front();
        x = w.x;
        y = w.y;
        q.pop();
        for(k = 0; k < 8; k++)
        {
            i = x + dx[k];
            j = y + dy[k];
            if(ok(i, j) && a[i][j] == 0 && (b[i][j] > b[x][y] + w1.cost || b[i][j] == 0 ))
            {
                if(k == 1 || k == 7) w1.cost = 1;
                else if(k == 2 || k == 6) w1.cost = 2;
                else if(k == 3 || k == 5) w1.cost = 3;
                else if(k == 4) w1.cost = 4;
                else if (k == 0) w1.cost = 0;
                b[i][j] = b[x][y]+ w1.cost;
                w1.x = i;
                w1.y = j;
                q.push(w1);
            }
        }
    }
}
int main()
{
    Read();
    Lee(xs, ys);
    ofstream fout("car.out");
    fout<<b[xf][yf]-b[xs][ys];
    /*for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            fout << b[i][j] << " ";
        fout << endl;
    }*/
    fout.close();
    return 0;
}