Cod sursa(job #1518550)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 5 noiembrie 2015 22:55:03
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

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;

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

queue < pair < pair < int , int > , int > > q;

bool limits(int x , int y)
{
    return (1 <= x && x <= n && 1 <= y && y <= m);
}

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]);

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

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

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

        ///move
        if (!a[l+dx[d]][c+dy[d]] && limits(l + dx[d] , c + dy[d]))
            if (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.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.push({{l , c} , (d+ind+8)%8});
    }

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

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

    return 0;
}