Cod sursa(job #2113111)

Utilizator calin1Serban Calin calin1 Data 24 ianuarie 2018 11:30:16
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <iostream>
#include <cstdio>
#define N 505
#define inf 0x3f3f3f3f

using namespace std;

int n, m, mat[N][N], vec[10], minim = inf;

int i_init, j_init, i_fin, j_fin;

int iv[] = {1, 1, 1, 0, -1, -1, -1, 0};
int jv[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int calculate_unghi(int i, int j)
{
    switch(i)
    {
    case 1:
        {
            switch(j)
            {
                case -1: return 1;
                case 0: return 2;
                case 1: return 3;
            }
        }

    case 0:
        {
            switch(j)
            {
                case 1: return 4;
                case -1: return 8;
            }
        }

    case -1:
        {
            switch(j)
            {
                case 1: return 5;
                case 0: return 6;
                case -1: return 7;
            }
        }

    }

    return 9;
}

int abs(int x)
{
    if(x > 0)
    {
        return x;
    }

    return -x;
}

int calculate_cost(int u_init, int u)
{
    int tmp = abs(u_init - u);

    switch(tmp)
    {
        case 5: return 3;
        case 6: return 2;
        case 7: return 1;
    }

    return tmp;
}

void solve(int i, int j, int cost, int unghi)
{
    if(i == i_fin && j == j_fin)
    {
        if(cost < minim)
        {
            minim = cost;
        }
    }

    mat[i][j] = 2;

    int ii, jj, tmp_unghi, tmp_cost;

    for(int v = 0 ; v < 8 ; ++v)
    {
        ii = i + iv[v];
        jj = j + jv[v];

        if(!mat[ii][jj])
        {
            tmp_unghi = calculate_unghi(iv[v], jv[v]);

            tmp_cost = calculate_cost(unghi, tmp_unghi);

            if(unghi == 0)
            {
                tmp_cost = 0;
            }

            solve(ii, jj, cost + tmp_cost, tmp_unghi);
        }
    }
}

void bordare()
{
    for(int i = 0 ; i <= m + 1 ; ++i)
    {
        mat[0][i] = 1;
        mat[n + 1][i] = 1;
    }

    for(int i = 0 ; i <= n + 1 ; ++i)
    {
        mat[i][0] = 1;
        mat[i][m + 1] = 1;
    }
}

void citire()
{
    scanf("%d %d\n", &n, &m);

    scanf("%d %d %d %d\n", &i_init, &j_init, &i_fin, &j_fin);

    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= m ; ++j)
        {
            scanf("%d ", &mat[i][j]);
        }

        scanf("\n");
    }
}

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

    citire();

    bordare();

    solve(i_init, j_init, 0, 0);

    printf("%d", minim);

    return 0;
}