Cod sursa(job #1053123)

Utilizator japjappedulapPotra Vlad japjappedulap Data 12 decembrie 2013 11:57:05
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define DIM 502
#define INF 999999999
ifstream is ("car.in");
ofstream os ("car.out");

struct Cel{int i, j;} Start, Finish;

queue <Cel> Q;
vector <vector <pair <int , Cel> > > V;

const int di[] = {-1,-1,0,1,1,1,0,-1};
const int dj[] = {0,1,1,1,0,-1,-1,-1};

bool a[DIM][DIM];
int D[DIM][DIM];
int n, m;

void Read();
void BFS();
bool Ok(int i, int j);
void DEBUG();

int main()
{


    is.close();
    os.close();
    return 0;
}


void Read()
{
    is >> n >> m;
    is >> Start.i >> Start.j >> Finish.i >> Finish.j;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            is >> a[i][j];
};

void BFS()
{
    Cel Ac;
    int i, j, iv, jv;
    Q.push(Start);

    D[Start.i][Start.j] = 1;
    while (!Q.empty())
    {
        Ac = Q.front(), Q.pop();
        i = Ac.i, j = Ac.j;
        for (int dir = 0; dir < 8; dir++)
        {
            iv = i + di[dir];
            jv = j + dj[dir];
            if (Ok(iv, jv) && D[iv][jv] == 0 && a[iv][jv] == 0)
            {
                D[iv][jv] = D[i][j]+1;
                Ac.i = iv, Ac.j = jv;
                Q.push(Ac);
                if (D[iv][jv] > 2)
                    V[D[iv][jv]].push_back(make_pair(INF, Ac));
                else
                    V[D[iv][jv]].push_back(make_pair(0, Ac));
            }
        }
    }
};

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

void DEBUG()
{

};