Cod sursa(job #1745222)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 21 august 2016 15:06:00
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 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];
	}
};
queue<nod> q;
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];
}

vector<queue<nod> > v;

int solve()
{
//	for (int d = 0; d < 8; d++)
//		best[si][sj][d] = 0;
	v.push_back(q);
	v.push_back(q);
    for (int d = 0; d < 8; d++) {
		int nx = si + dx[d];
		int ny = sj + dy[d];
        if (good(nx, ny)) {
			v[0].push(nod(nx, ny, d));
			best[nx][ny][d] = 0;
        }
    }
	while (true) {
        if (v[0].empty()) {
			v.erase(v.begin());
            v.push_back(q);
        }
        if (v[0].empty()) break;
        nod top = v[0].front();
        v[0].pop();
        for (int i = top.dir-1; i <= top.dir+1; i++) {
			int d = (i >= 0 && i < 8) ? i : 8-i;
			int nx = top.x + dx[d];
			int ny = top.y + dy[d];
			int cost = abs(top.dir - i);
            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;
				v[cost].push(nod(nx, ny, d));
				if (nx == fi && ny == fj)
					return best[nx][ny][d];
            }
            if (cost && best[top.x][top.y][top.dir] + cost < best[top.x][top.y][d]) {
				best[top.x][top.y][d] = best[top.x][top.y][top.dir] + cost;
                v[cost].push(nod(top.x, top.y, 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;
}