Cod sursa(job #2094756)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 26 decembrie 2017 15:19:43
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <fstream>
#include <queue>
#include <bitset>

using namespace std;

ofstream fout ("car.out");

class InputReader {
	public:
        InputReader() {}
        InputReader(const char *name) {
            fin = fopen(name, "r");
			buffpos = Size - 1;
        }
        inline InputReader &operator >>(int &n) {
			char ch = nextpos();
            while(ch < '0' || ch > '9') {
                ch = nextpos();
            }

            n = 0;
            while('0' <= ch && ch <= '9') {
                n = n * 10 + ch - '0';
                ch = nextpos();
            }
            return *this;
        }
    private:
        FILE *fin;
        static const int Size = 1 << 17;
        int buffpos;
        char buff[Size];

        inline char nextpos() {
            ++ buffpos;
            if(buffpos == Size) {
                buffpos = 0;
                fread(buff, Size, 1, fin);
            }
			return buff[ buffpos ];
        }
} fin ("car.in");

const int nmax = 500;
const int inf = 1 << 30;
const int dl[ 8 ] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dc[ 8 ] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n, m, ram;
int v[nmax + 2][nmax + 2];

int stx, sty, fnx, fny;

int d[nmax + 1][nmax + 1][ 8 ];
bitset< 8 > gata[nmax + 1][nmax + 1];

struct str {
    int x, y, k;

    str () {}
    str (int _x, int _y, int _k) {
        x = _x, y = _y, k = _k;
    }
};

queue< str > q[ 5 ];

inline int cst (int x, int y) {
    if (x > y) swap(x, y);
    return min(y - x, 8 - y + x);
}

void extinde (str p, int ind) {
    for (int dir = 0; dir < 8; ++ dir) {
        int x = p.x + dl[ dir ], y = p.y + dc[ dir ];

        if (gata[ x ][ y ][ dir ] == 1 || v[ x ][ y ] == 1)
            continue;

        int c = cst(p.k, dir);
        if (d[ x ][ y ][ dir ] > d[ p.x ][ p.y ][ p.k ] + c) {
            ++ ram;

            d[ x ][ y ][ dir ] = d[ p.x ][ p.y ][ p.k ] + c;
            q[(ind + c) % 5].push(str(x, y, dir));
        }
    }
}

void bfs () {
    ram = 0;

    for (int i = 0; i < 8; ++ i) {
        d[ stx ][ sty ][ i ] = 0;
        ++ ram;
        q[ 0 ].push(str(stx, sty, i));
    }

    int ind = 0;
    while (ram > 0) {
        while (q[ ind ].empty()) {
            ind = (ind + 1) % 5;
        }

        str p = q[ ind ].front(); q[ ind ].pop();
        -- ram;

        if (gata[ p.x ][ p.y ][ p.k ] == 1)
            continue;
        gata[ p.x ][ p.y ][ p.k ] = 1;

        extinde(p, ind);
    }
}

int main () {
    fin >> n >> m >> stx >> sty >> fnx >> fny;

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            fin >> v[ i ][ j ];
        }
    }

    for (int i = 0; i <= n + 1; ++ i)
        v[ i ][ 0 ] = v[ i ][m + 1] = 1;
    for (int i = 0; i <= m + 1; ++ i)
        v[ 0 ][ i ] = v[n + 1][ i ] = 1;


    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            for (int k = 0; k < 8; ++ k)
                d[ i ][ j ][ k ] = inf;

    bfs();


    int ans = inf;
    for (int i = 0; i < 8; ++ i)
        ans = min(ans, d[ fnx ][ fny ][ i ]);

    if (ans == inf)
        ans = -1;

    fout << ans << "\n";

    fout.close();
    return 0;
}