Official Analysis (Java)

Explanation

Each fence can be thought of as two grid units. The reason we use two is for cases such as $NESW$. If we only use one grid unit per fence, there would be no area inside it, and thus we would undercount.

We can model the fences, and floodfill to find the number of connected components. The region not enclosed by a fence is also counted as one connected component. By merging the regions enclosed by a fence with the region not enclosed by the fence, by means of a gate, we can ensure the farm is connected. The cows are able to go from a region enclosed by a fence into the region not enclosed by a fence and subsequently visit another region which is enclosed by a fence.

Therefore, the number of gates that must be used is equal to the number of regions enclosed by the fence, which is the number of connected components minus one.

We can perform floodfill and have the fences signify a stopping point. If a fence is seen, we no longer continue to floodfill in that direction. This is because floodfill is performed to simulate the cows' movement, and a cow cannot walk through a fence.

To count the number of connected components, we perform floodfill from every point in our boundaries (more on that in the warning below). If we have already visited a point, we don't floodfill any further. If we have to start a new floodfill, it means the point we're starting on was not reached from prior floodfills, meaning it is in a separate component. Thus, we add one to our count of connected components.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
void ff(int i, int j);

bool fence[4003][4003] = {false};
bool visited[4003][4003] = {false};
int maxx = 2001, minx = 2001, maxy = 2001, miny = 2001;
int main() {

Copy
import java.io.*;
import java.util.*;

public class BuildGates {
	private static final Map<Character, int[]> DIR = new HashMap<>() {
		{
			put('N', new int[] {-1, 0});
			put('S', new int[] {1, 0});
			put('E', new int[] {0, 1});
			put('W', new int[] {0, -1});

Alternate Faster Solution

It is possible to make the following 2 observations:

1. For each contiguous closed region, there must be 1 gate. In a minimum state, each region has exactly 1 gate. For example, if there are 2 regions, there must be 2 gates.
2. Each time FJ comes across a node he has visited along an edge he has not crossed in either direction, he creates exactly 1 new region. In other words, FJ creates exactly 1 new contiguous closed region if all of these conditions are met:

   • FJ walks along an edge from point $a$ to $b$
   • He did not walk from $a$ to $b$ in the past
   • He did not walk from $b$ to $a$ in the past
   • $b$ is a point he had already visited

Under these observations, we can use a set of visited edges and visited nodes, and keep track of the number of contiguous closed regions. This solution is about 10 times faster than flood filling due to $\log N$ lookup and insertion.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

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

int main() {
	freopen("gates.in", "r", stdin);
	freopen("gates.out", "w", stdout);

	ios::sync_with_stdio(0);
	cin.tie(0);

Copy
with open("gates.in") as read:
	n = int(read.readline().strip())
	s = read.readline().strip()

visedge = set()
visnode = set()

prev = (0, 0)
visnode.add(prev)
ans = 0