#include <iostream>
#include <list>
#include <windows.h>

using namespace std;

typedef pair<int, int> Coords;

Coords arrivee(499, 499);
Coords depart(0, 0);

std::list<Coords> liste_ouverte;

char tableau[500][500] = {0};

void ajouter_cases_adjacentes(Coords &curseur)
{
    Coords ctmp;

    ctmp.first = curseur.first - 1;
    ctmp.second = curseur.second;
    if(!(ctmp.first < 0 || ctmp.second < 0 || ctmp.first > 499 || ctmp.second > 499 || tableau[ctmp.first][ctmp.second] == 2
            || tableau[ctmp.first][ctmp.second] == 1))
        liste_ouverte.push_back(ctmp);

    ctmp.first = curseur.first;
    ctmp.second = curseur.second + 1;
    if(!(ctmp.first < 0 || ctmp.second < 0 || ctmp.first > 499 || ctmp.second > 499 || tableau[ctmp.first][ctmp.second] == 2
            || tableau[ctmp.first][ctmp.second] == 1))
        liste_ouverte.push_back(ctmp);

    ctmp.first = curseur.first + 1;
    ctmp.second = curseur.second;
    if(!(ctmp.first < 0 || ctmp.second < 0 || ctmp.first > 499 || ctmp.second > 499 || tableau[ctmp.first][ctmp.second] == 2
            || tableau[ctmp.first][ctmp.second] == 1))
        liste_ouverte.push_back(ctmp);

    ctmp.first = curseur.first;
    ctmp.second = curseur.second - 1;
    if(!(ctmp.first < 0 || ctmp.second < 0 || ctmp.first > 499 || ctmp.second > 499 || tableau[ctmp.first][ctmp.second] == 2
            || tableau[ctmp.first][ctmp.second] == 1))
        liste_ouverte.push_back(ctmp);
}

void parcourir_liste(Coords &curseur)
{
    curseur = liste_ouverte.front();
}

int main()
{
    DWORD deb = GetTickCount();
    liste_ouverte.push_back(depart);

    Coords curseur(depart);

    while(curseur != arrivee && !liste_ouverte.empty())
    {
        tableau[curseur.first][curseur.second] = 2;
        liste_ouverte.remove(curseur);
        ajouter_cases_adjacentes(curseur);
        parcourir_liste(curseur);
    }
    DWORD fin = GetTickCount();

    cout << fin - deb << endl;
    return 0;
}