Cod sursa(job #1987950)

Utilizator giotoPopescu Ioan gioto Data 1 iunie 2017 16:21:50
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.04 kb
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
int n, m, l1, c1, l2, c2, a[505][505], t[505][505][8], st[3], dr[3];
int q[3][1000005];
struct coada{
    int l, c, d;
}z;
short dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
short dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
inline int cost(int d1, int d2){
    int dif = abs(d2 - d1);
    return min(8 - dif, dif);
}
inline void bfs(){
    st[0] = st[1] = st[2] = 1; dr[0] = 0;
    int k = 0;
    for(short kr = 0; kr < 8 ; ++kr){
        if(a[l1 + dx[kr]][c1 + dy[kr]] == 1 && l1 + dx[kr] >= 0 && l1 + dx[kr] <= n && c1 + dy[kr] >= 0 && c1 + dy[kr] <= m) continue ;
        t[l1][c1][kr] = 0;
        q[0][++dr[k]] = (l1 << 9) + c1 + (kr << 18);
    }
    while(st[0] <= dr[0] || st[1] <= dr[1] || st[2] <= dr[2]){
        while(st[k] > dr[k]){
            ++k;
            if(k > 2) k = k - 3;
        }
        int x = q[k][st[k]++];
        z.d = x >> 18;
        z.c = (x & 511); z.l = (x >> 9) & 511;
        short cr = z.d, steps = 0, ok = 0, usu = 0;
        while(steps <= 2){
            short l = dx[cr] + z.l;
            short c = dy[cr] + z.c;
            if(l >= 1 && c >= 1 && l <= n && c <= m && a[l][c] == 0){
                if(t[l][c][cr] > t[z.l][z.c][z.d] + usu){
                    t[l][c][cr] = t[z.l][z.c][z.d] + usu;
                    if(l == l2 && c == c2)
                        break ;
                    int newk = (k + usu);
                    if(newk > 2) newk -= 3;
                    q[newk][++dr[newk]] = (l << 9) + c + (cr << 18);
                }
            }
            ++steps; ++cr; ++usu;
            if(cr == 8) cr = 0;
        }
        cr = z.d - 1; steps = 0; usu = 1;
        if(ok == 1) steps = 2;
        while(steps <= 1){
            if(cr < 0) cr = 7;
            short l = dx[cr] + z.l;
            short c = dy[cr] + z.c;
            if(l >= 1 && c >= 1 && l <= n && c <= m && a[l][c] == 0){
                if(t[l][c][cr] > t[z.l][z.c][z.d] + usu){
                    t[l][c][cr] = t[z.l][z.c][z.d] + usu;
                    if(l == l2 && c == c2)
                        break ;
                    int newk = (k + usu);
                    if(newk > 2) newk -= 3;
                    q[newk][++dr[newk]] = (l << 9) + c + (cr << 18);
                }
            }
            ++steps; --cr; ++usu;
        }
    }
}
int main()
{
    InParser fin("car.in");
    ofstream fout("car.out");
    fin >> n >> m;
    fin >> l1 >> c1 >> l2 >> c2;
    for(int i = 1; i <= n ; ++i)
        for(int j = 1; j <= m ; ++j){
            fin >> a[i][j];
            for(short k = 0; k < 8 ; ++k)
            t[i][j][k] = 2000000000;
        }
    bfs();
    int Sol = 2000000000;
    for(short k = 0; k < 8 ; ++k)
        Sol = min(Sol, t[l2][c2][k]);
    if(Sol == 2000000000) fout<<"-1";
    else fout << Sol;
    return 0;
}