Cod sursa(job #1745142)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 21 august 2016 13:10:19
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <cstdio>
#include <queue>
#define MAXN 550
#define inf 0x3fffffff

using namespace std;


int n, m;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int best[MAXN][MAXN][8];
int a[MAXN][MAXN];
struct nod
{
    int x, y, dir;
    nod(int x = 0, int y = 0, int dir = 0) : x(x), y(y), dir(dir) { }
	bool operator()(nod a, nod b)
	{
        return best[a.x][a.y][a.dir] > best[b.x][b.y][b.dir];
	}
};
priority_queue<nod, vector<nod>, nod> heap;
int si, sj, fi, fj, rez;
inline bool good(int nx, int ny)
{
    return nx > 0 && nx <= n && ny > 0 && ny <= m && !a[nx][ny];
}
int solve()
{
    for (int d = 0; d < 8; d++) {
		int nx = si + dx[d];
		int ny = sj + dy[d];
        if (good(nx, ny)) {
			heap.push(nod(nx, ny, d));
			best[nx][ny][d] = 0;
        }
    }
    while (!heap.empty()) {
        nod top = heap.top();
        heap.pop();
        if (top.x == fi && top.y == fj)
			return best[top.x][top.y][top.dir];
        for (int d = 0; d < 8; d++) {
			int nx = top.x + dx[d];
			int ny = top.y + dy[d];
			int cost =  abs(d-top.dir);
            if (good(nx, ny) && best[top.x][top.y][top.dir] + cost < best[nx][ny][d]) {
				best[nx][ny][d] = best[top.x][top.y][top.dir] + cost;
				heap.push(nod(nx, ny, d));
            }
        }
    }
    return -1;
}

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

	scanf("%d %d", &n, &m);
	scanf("%d %d %d %d", &si, &sj, &fi, &fj);
    for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
	for (int i = 0; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int d = 0; d < 8; d++)
				best[i][j][d] = inf;
	rez = solve();
	printf("%d", rez);

    return 0;
}