USACO 2016 January Contest Silver Division - Build Gates

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be done in several ways, but the two most relevant solutions for this problem consist in either doing a flood fill where we build the fence and then check the number of regions we got, as we will have to build gates between the regions which are not connected.

Because the fence is small, we can build the fence directly and then count the number of distinct regions Farmer John's farm is broken up into using floodfill. If it is broken up into \(N\) distinct regions, then Farmer John needs to build \(N − 1\) gates, since a gate can only connect make it possible to travel between two regions.

In terms of storing the fence, we opt to use a two-dimensional array of booleans to track which locations have fence built on them. Instead of having fence pieces be unit length, we double the length of the fence. Therefore, distinct squares of the fence are at points \((x, y)\) where both \(x\) and \(y\) are odd, and to check if there is a fence between those two points, you simply inspect the point in between.

Alternatively, we can solve the problem by noting that the fence built by FJ forms a single connected planar graph (each move adds an edge and a vertex, and the entire path is connected). For any connected planar graph, Euler’s formula tells us that \(V − E + F = 2\), where V is the number of vertices, E is the number of unique edges, and F is the total number of faces (regions) including the unbounded outer region. Thus, the number of “enclosed” regions (the ones inside the fence) is \(F – 1 = (E – V + 2) – 1 = E – V + 1\).

Each enclosed region is isolated from the others by fences, so to connect all regions together we need to add one gate per enclosed region. (If there are no enclosed regions, no gate is needed.) Therefore, the answer is simply the difference between the number of unique edges and number of unique vertices to which we add \(1\).

Source code (floodfill method)

The source code in C++ can be seen below, based on the implementation shown here.

#include <fstream>
#include <map>
using namespace std;

bool fence[4003][4003], visited[4003][4003];
int maxx = 2001, minx = 2001, maxy = 2001, miny = 2001;

void ff(int i, int j) {
    if (i < minx || i > maxx || j < miny || j > maxy || visited[i][j] || fence[i][j]) {
        return;
    }
    visited[i][j] = true;
    int x[] = {-1, 0, 0, 1}, y[] = {0, -1, 1, 0};
    for (int k = 0; k < 4; k++) {
        ff(i + x[k], j + y[k]);
    }
}

int main() {
    ifstream cin ("gates.in");
    ofstream cout ("gates.out");
    int n;
    string path;
    cin >> n >> path;
    int x = 2001, y = 2001;
    map<char, pair<int, int>> dir{{'N', {-1, 0}}, {'S', {1, 0}}, {'E', {0, 1}}, {'W', {0, -1}}};
    for (int i = 0; i < n; i++) {
        fence[x + dir[path[i]].first][y + dir[path[i]].second] = true;
        fence[x + 2 * dir[path[i]].first][y + 2 * dir[path[i]].second] = true;
        x += 2 * dir[path[i]].first;
        y += 2 * dir[path[i]].second;
        minx = min(minx, x);
        maxx = max(maxx, x);
        miny = min(miny, y);
        maxy = max(maxy, y);
    }
    minx--;
    maxx++;
    miny--;
    maxy++;
    int regions = 0;
    for (int i = minx; i <= maxx; i++) {
        for (int j = miny; j <= maxy; j++) {
            if (!visited[i][j] && !fence[i][j]) {
                ff(i, j);
                regions++;
            }
        }
    }
    cout << regions - 1 << '\n';
    return 0;
}

Source code (Euler method)

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

#include <fstream>
#include <set>
#include <string>
#include <tuple>

using namespace std;

int main() {
    ifstream cin("gates.in");
    ofstream cout("gates.out");

    int N;
    cin >> N;
    string path;
    cin >> path;

    set<pair<int, int>> vertices;
    set<tuple<int, int, int, int>> edges;

    int x = 0, y = 0;
    vertices.insert({x, y});

    for (char dir : path) {
        int nx = x, ny = y;
        if (dir == 'N')
            ny++;
        else if (dir == 'S')
            ny--;
        else if (dir == 'E')
            nx++;
        else if (dir == 'W')
            nx--;

        vertices.insert({nx, ny});
        int x1 = x, y1 = y, x2 = nx, y2 = ny;
        if (make_pair(x2, y2) < make_pair(x1, y1)) {
            swap(x1, x2);
            swap(y1, y2);
        }
        edges.insert({x1, y1, x2, y2});
        x = nx;
        y = ny;
    }
    cout << edges.size() - vertices.size() + 1 << "\n";

    return 0;
}