USACO 2015 December Contest Gold Division - Bessie's Dream

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Most of the problem is pretty straightforward, it's just the purple tile which causes more difficulties. First, let's define its rules a little more clearly:

When we're on a purple tile, we must move in the same direction as our last move if possible, so for each state, we just need to store the previous direction

• direction is undefined for the starting state, but it doesn't matter because it's always pink
• just suppose that dir is north, for all other positions, direction is defined

Therefore, we can use these rules in order to run a BFS-styled approach in order to solve the problem.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

const array<int, 4> dr = {-1, 0, 1, 0};
const array<int, 4> dc = {0, 1, 0, -1};

struct State {
    int r, c, dir;
    bool smell;

    State(int r, int c, int dir, bool smell) :
        r(r), c(c), dir(dir), smell(smell) {
    }

    int pack() {
        return r * 8000 + c * 8 + dir * 2 + smell;
    }

    static State unpack(int x) {
        return State(x / 8000, x % 8000 / 8, x % 8 / 2, x & 1);
    }
};

int main() {
#ifndef HOME
    freopen("dream.in", "r", stdin);
    freopen("dream.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    auto get_col = [&](int r, int c) {
        return r >= 0 && r < n && c >= 0 && c < m ? a[r][c] : 0;
    };

    vector<int> dist(8000000, INF); dist[0] = 0;
    queue<int> q; q.push(0);

    while (!q.empty()) {
        State u = State::unpack(q.front());
        q.pop();

        int col = get_col(u.r + dr[u.dir], u.c + dc[u.dir]);

        if (a[u.r][u.c] == 4 && col != 0 && col != 3) {
            State v = State(u.r + dr[u.dir], u.c + dc[u.dir], u.dir, col == 2);

            if (dist[v.pack()] == INF) {
                dist[v.pack()] = dist[u.pack()] + 1;
                q.push(v.pack());
            }

            continue;
        }

        for (int i = 0; i < 4; i++) {
            col = get_col(u.r + dr[i], u.c + dc[i]);

            if (col != 0 && (col != 3 || u.smell)) {
                State v = State(u.r + dr[i], u.c + dc[i], i, col == 2 || (u.smell && col != 4));

                if (dist[v.pack()] == INF) {
                    dist[v.pack()] = dist[u.pack()] + 1;
                    q.push(v.pack());
                }
            }
        }
    }

    int ans = INF;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 2; j++) {
            ans = min(ans, dist[State(n - 1, m - 1, i, j).pack()]);
        }
    }
    cout << (ans == INF ? -1 : ans) << '\n';

    return 0;
}