Cod sursa(job #1703433)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 16 mai 2016 22:05:54
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

const int dim = 505;
const int inf = 0x3f3f3f3f;
const int dx[] = { 1, 1, 1, 0, -1, -1, -1, 0 };
const int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };	 

int a[dim][dim], dp[dim][dim][8];

queue<int> que[2];

inline int makeState(int x, int y, int dir) {
	return (dir << 18) + (x << 9) + y;
}

inline int getX(int state) {
	return (state >> 9) & ((1 << 9) - 1);
}

inline int getY(int state) {
	return state & ((1 << 9) - 1);
}

inline int getDir(int state) {
	return state >> 18;
}

int main() {

	int n, m, startX, startY, finishX, finishY;
	fin >> n >> m >> startX >> startY >> finishX >> finishY;

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			fin >> a[i][j];
			for (int dir = 0; dir < 8; ++dir)
				dp[i][j][dir] = inf;
		}
	}
	
	int now = 0, nxt = 1;
	for (int dir = 0; dir < 8; ++dir) {
		que[now].push(makeState(startX, startY, dir));
		dp[startX][startY][dir] = 0;
	}

	int sol = -1;
	for (int cost = 0; !(que[0].empty() && que[1].empty()) && sol == -1; ++cost, swap(now, nxt)) {
		while (!que[now].empty() && sol == -1) {

			int cur = que[now].front();
			que[now].pop();

			int x = getX(cur);
			int y = getY(cur);
			int dir = getDir(cur);

			if (x == finishX && y == finishY) {
				sol = cost;
				continue;
			}

			int nxtX = x + dx[dir];
			int nxtY = y + dy[dir];
			if (1 <= nxtX && nxtX <= n && 1 <= nxtY && nxtY <= m && a[nxtX][nxtY] == 0 && cost < dp[nxtX][nxtY][dir]) {
				dp[nxtX][nxtY][dir] = cost;
				que[now].push(makeState(nxtX, nxtY, dir));
			}

			int nxtDir = (dir + 1) % 8;
			if (cost + 1 < dp[x][y][nxtDir]) {
				dp[x][y][nxtDir] = cost + 1;
				que[nxt].push(makeState(x, y, nxtDir));
			}

			nxtDir = (dir + 7) % 8;
			if (cost + 1 < dp[x][y][nxtDir]) {
				dp[x][y][nxtDir] = cost + 1;
				que[nxt].push(makeState(x, y, nxtDir));
			}

		}
	}

	fout << sol << '\n';

	return 0;

}

//Trust me, I'm the Doctor!