Cod sursa(job #1547128)

Utilizator theprdvtheprdv theprdv Data 9 decembrie 2015 02:17:45
Problema Car Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>

#define MAXN 512
#define next_square_pos(x) ( ((x) + 1) <  8 ? (x) + 1 : 0 )
#define prev_square_pos(x) ( ((x) - 1) >= 0 ? (x) - 1 : 7 )


typedef struct {
    int i, j, prev_i, prev_j, prev_sq_pos;
} queue;

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

int N, M, HEAD, TAIL, fin_i, fin_j, min_cost = 0x3f3f3f3f;
unsigned int map[MAXN][MAXN][8];
bool active[MAXN][MAXN];
queue Q[MAXN * MAXN * 8];


void add_to_queue(int i, int j, int prev_i, int prev_j, int sq_pos)
{
    Q[TAIL].i = i, Q[TAIL].j = j;
    Q[TAIL].prev_i = prev_i, Q[TAIL].prev_j = prev_j;
    Q[TAIL].prev_sq_pos = sq_pos;
    ++TAIL;
}


void update_cost(int i, int j, int prev_i, int prev_j, int cost, int sq_pos)
{
    int prev_sq_pos = Q[HEAD].prev_sq_pos;

    if (map[prev_i][prev_j][prev_sq_pos] + cost > map[i][j][sq_pos] && map[i][j][sq_pos]) return;   /* we have a better cost */
    if (i <= 0 || j <= 0 || i > N || j > M) return; /* out of map */
    if (!active[i][j]) return;

    map[i][j][sq_pos] = map[prev_i][prev_j][prev_sq_pos] + cost;
    add_to_queue(i, j, prev_i, prev_j, sq_pos);
    if (i == fin_i && j == fin_j && map[i][j][sq_pos] < min_cost)
        min_cost = map[i][j][sq_pos];
}


int get_square_pos(int i, int j, int by_i, int by_j)
{
    int k;
    for (k = 0; k < 8; ++k)
        if (i + dx[k] == by_i && j + dy[k] == by_j) break;
    return k;
}


int main(int argc, char *argv[])
{
	assert(freopen("car.in", "r", stdin));
	freopen("car.out", "w", stdout);

	int ini_i, ini_j, i, j;

	/* read the input data */
	scanf("%d%d", &N, &M);
	scanf("%d%d%d%d", &ini_i, &ini_j, &fin_i, &fin_j);
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j) {
            scanf("%d", &active[i][j]);
            active[i][j] = !active[i][j];
		}

	/* init */
    for (i = 0; i < 8; ++i)
        update_cost(ini_i + dy[i], ini_j + dx[i], ini_i, ini_j, 0, i);


    while (HEAD < TAIL) {
        int sq_pos = get_square_pos(Q[HEAD].i, Q[HEAD].j, Q[HEAD].prev_i, Q[HEAD].prev_j);
        int next = next_square_pos(sq_pos);
        int prev = prev_square_pos(sq_pos);
        int i;

        /* 90 and 45 */
        for (i = 0; i < 2; ++i) {
            next = next_square_pos(next);
            prev = prev_square_pos(prev);
            update_cost(Q[HEAD].i + dy[next], Q[HEAD].j + dx[next], Q[HEAD].i, Q[HEAD].j, !i ? 2 : 1, next);
            update_cost(Q[HEAD].i + dy[prev], Q[HEAD].j + dx[prev], Q[HEAD].i, Q[HEAD].j, !i ? 2 : 1, prev);
        }

        /* 0 */
        next = next_square_pos(next);
        update_cost(Q[HEAD].i + dx[next], Q[HEAD].j + dy[next], Q[HEAD].i, Q[HEAD].j, 0, next);


        ++HEAD; /* pop the queue */
    }

    printf("%d\n", min_cost);
	return 0;
}