Cod sursa(job #1518557)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 5 noiembrie 2015 23:02:12
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
///sursa urata

#include <bits/stdc++.h>

using namespace std;

const int dx[8] = {0 , -1 , -1 , -1 , 0 , 1 , 1 , 1};
const int dy[8] = {1 , 1 , 0 , -1 , -1 , -1 , 0 , 1};

const int Nmax = 500 + 10;
const int inf = 0x3f3f3f3f;

int n , m , i , j , ind , crt;
int p[2][2] , a[Nmax][Nmax];
int dp[8][Nmax][Nmax];

queue < pair < pair < int , int > , int > > q[2];

int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);

    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &p[0][0] , &p[0][1] , &p[1][0] , &p[1][1]);

    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]), a[i][j] ^= 1;

    memset(dp , inf , sizeof(dp));

    for (ind = 0; ind < 8; ++ind)
        q[0].push({{p[0][0] , p[0][1]} , ind}),
        dp[ind][p[0][0]][p[0][1]] = 0;

    while (!q[crt].empty() || !q[crt].empty())
    {
        int l , c , d;
        tie(l , c) = q[crt].front().first; d = q[crt].front().second;
        q[crt].pop();

        ///move
        if (a[l+dx[d]][c+dy[d]] && dp[d][l][c] < dp[d][l+dx[d]][c+dy[d]])
                dp[d][l+dx[d]][c+dy[d]] = dp[d][l][c],
                q[crt].push({{l+dx[d],c+dy[d]},d});

        ///change dir
        for (ind = -1; ind <= 1; ind += 2)
            if (dp[(d+ind+8)%8][l][c] > dp[d][l][c] + 1)
                dp[(d+ind+8)%8][l][c] = dp[d][l][c] + 1,
                q[!crt].push({{l , c} , (d+ind+8)%8});

        if (q[crt].empty()) crt ^= 1;
    }

    int ans = inf;
    for (ind = 0; ind < 8; ++ind)
        ans = min(ans , dp[ind][p[1][0]][p[1][1]]);

    (ans == inf) ? printf("-1\n") : printf("%d\n", ans);

    return 0;
}