January 2006 Problem 'grove' Analysis

by Bruce Merry

This is a shortest-path problem with a twist. The trick is to modify the search space to force a circumnavigation of the island. One way to simplify the problem is to draw a line between the island and the border of the pasture, and require that path cross this line and only in one direction. Such a line can be found quite easily by taking the corner of the grove that is top-most then right-most, and joining it to the right border (note that the line passes between the rows of the grid). Now instead of walking in a space of (X, Y) coordinates, you can walk in a space of (X, Y, C) coordinates, were C is 0 if the line has not yet been crossed and 1 if it has. It is also necessary to disallow any steps that cross the line in the wrong direction.

#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <cassert>

using namespace std;

#define MAXR 50
#define MAXC 50

static int R, C;
static int Sr = -1, Sc = -1;
static int Ir = -1, Ic = -1;
static char grid[MAXR][MAXC + 1];
static int label[MAXR][MAXC];
static int Z;

static const int dr[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
static const int dc[8] = {0, -1, 0, 1, -1, 1, -1, 1};

static void label_dfs(int r, int c, int l, bool diag) {
    int m = diag ? 8 : 4;
    label[r][c] = l;
    for (int d = 0; d < m; d++) {
        int r2 = r + dr[d];
        int c2 = c + dc[d];
        if (r2 >= 0 && r2 < R && c2 >= 0 && c2 < C
            && grid[r2][c2] == grid[r][c] && label[r2][c2] != label[r][c])
            label_dfs(r2, c2, l, diag);
    }
}

static void validate() {

    memset(label, 0, sizeof(label));
    label_dfs(Sr, Sc, 1, true);
    label_dfs(Ir, Ic, 2, false);

    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
        {
            if (i == 0 || i == R - 1 || j == 0 || j == C - 1)
                assert(label[i][j] == 1);
            if (grid[i][j] == 'X') assert(label[i][j] == 2);
        }
}

struct point {
    int r, c;
    int wind;

    point() {}
    point(int r, int c, int w) : r(r), c(c), wind(w) {}
};

static void solve() {
    queue<point> q;
    int prio[R][C][2];
    point parent[R][C][2];

    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            prio[i][j][0] = prio[i][j][1] = INT_MAX;

    prio[Sr][Sc][0] = 0;
    q.push(point(Sr, Sc, 0));
    while (!q.empty()) {
        point cur = q.front();
        int p = prio[cur.r][cur.c][cur.wind];
        q.pop();
        for (int d = 0; d < 8; d++) {
            point nxt(cur.r + dr[d], cur.c + dc[d], cur.wind);
            if (nxt.r < 0 || nxt.r >= R || nxt.c < 0 || nxt.c >= C) continue;
            if (grid[nxt.r][nxt.c] == 'X') continue;
            if (cur.r == Ir - 1 && nxt.r == Ir && nxt.c < Ic) continue;
            if (cur.r == Ir && nxt.r == Ir - 1 && cur.c < Ic) {
                nxt.wind++;
                if (nxt.wind > 1) continue;
            }
            if (p + 1 < prio[nxt.r][nxt.c][nxt.wind]) {
                prio[nxt.r][nxt.c][nxt.wind] = p + 1;
                q.push(nxt);
                parent[nxt.r][nxt.c][nxt.wind] = cur;
            }
        }
    }

    Z = prio[Sr][Sc][1];
    assert(Z != INT_MAX);
    point cur(Sr, Sc, 1);
    while (cur.r != Sr || cur.c != Sc || cur.wind != 0) {
        cur = parent[cur.r][cur.c][cur.wind];
        grid[cur.r][cur.c] = '+';
    }
    grid[Sr][Sc] = '*';
}

int main()
{
    ifstream in("grove.in");

    in >> R >> C;
    for (int i = 0; i < R; i++) {
        in >> grid[i];
        assert(strlen(grid[i]) == (size_t) C);
        for (int j = 0; j < C; j++) {
            if (grid[i][j] == '*') {
                assert(Sr == -1);
                Sr = i;
                Sc = j;
                grid[i][j] = '.';
            }
            assert(grid[i][j] == '.' || grid[i][j] == 'X');
            if (grid[i][j] == 'X' && Ir == -1) {
                Ir = i;
                Ic = j;
            }
        }
    }

    validate();
    solve();

    ofstream out("grove.out");
    out << Z << "\n";
    return 0;
}