Solution for USACO 2015 December Gold #3: Dream

dream.cpp

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, int> state; // ((x y) o)
typedef pair<int, state> tstate;
#define MAXN 1005
#define MAXM 1005
#define INF 1<<30
int N, M;
int grid[MAXN][MAXM];
int dist[MAXN][MAXM][2]; // (x y orange)
bool visited[MAXN][MAXM][2];
priority_queue<tstate, vector<tstate>, greater<tstate> > pq;
int dxs[4] = {0, 1, 0, -1};
int dys[4] = {1, 0, -1, 0};

bool ok(int nx, int ny, int o) {
	if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
		return false;
	}
	if (grid[nx][ny] == 0) {
		return false;
	}
	if (grid[nx][ny] == 3 && o == 0) {
		return false;
	}
	return true;
}

void more(int t, int x, int y, int o) {
	if (t < dist[x][y][o]) {
		dist[x][y][o] = t;
		pq.push({t, {{x, y}, o}});
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	freopen("dream.in", "r", stdin);
	freopen("dream.out", "w", stdout);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> grid[i][j];
			dist[i][j][0] = dist[i][j][1] = INF;
		}
	}

	// dijkstra
	dist[0][0][0] = 0;
	pq.push({0, {{0, 0}, 0}});
	while (!pq.empty()) {
		tstate ts = pq.top();
		pq.pop();
		int t = ts.first;
		int x = ts.second.first.first;
		int y = ts.second.first.second;
		int o = ts.second.second;
		if (visited[x][y][o]) {
			continue;
		}
		visited[x][y][o] = true;
		for (int m = 0; m < 4; m++) {
			int dx = dxs[m];
			int dy = dys[m];
			int nx = x + dx;
			int ny = y + dy;
			if (!ok(nx, ny, o)) {
				continue;
			}
			if (grid[nx][ny] == 1 || grid[nx][ny] == 3) {
				more(t + 1, nx, ny, o);
			}
			else if (grid[nx][ny] == 2) {
				more(t + 1, nx, ny, 1);
			}
			else if (grid[nx][ny] == 4) {
				int amt = 1;
				do {
					nx += dx;
					ny += dy;
					amt += 1;
				} while(ok(nx, ny, 0) && grid[nx][ny] == 4);
				if (ok(nx, ny, 0)) {
					if (grid[nx][ny] == 2) {
						more(t + amt, nx, ny, 1);
					}
					else if (grid[nx][ny] == 1) {
						more(t + amt, nx, ny, 0);
					}
					else {
						cerr << "even bigger fatal error" << endl;
					}
				}
				else {
					nx -= dx;
					ny -= dy;
					amt -= 1;
					more(t + amt, nx, ny, 0);
				}
			}
			else {
				cerr << "looks like we've got a fatal error" << endl;
			}
		}
	}

	int d = min(dist[N - 1][M - 1][0], dist[N - 1][M - 1][1]);
	cout << (d == INF ? -1 : d) << endl;
	return 0;
}