Counting Closed Regions in a Path Using Euler's Formula

The Problem

Imagine you’re given a sequence of directions (N, S, E, W) that describe a path on a 2D grid starting from the origin (0, 0). As you follow this path, you might cross your own trail, creating closed regions or “loops” in the plane.

Question: How many closed regions does your path create?

This seemingly simple question leads us to a beautiful application of graph theory and one of the most elegant formulas in discrete mathematics: Euler’s Formula for Planar Graphs.

A Concrete Example

Let’s trace through the path: NNNESWWWSSEEEE

Starting from (0,0), we move:

NNN: up 3 steps → (0,3)
E: right → (1,3)
S: down → (1,2)
WWW: left 3 steps → (-2,2)
SS: down 2 steps → (-2,0)
EEEE: right 4 steps → (2,0)

graph LR
    A["(0,0)"] --> B["(0,1)"]
    B --> C["(0,2)"]
    C --> D["(0,3)"]
    D --> E["(1,3)"]
    E --> F["(1,2)"]
    F --> G["(0,2)"]
    G --> H["(-1,2)"]
    H --> I["(-2,2)"]
    I --> J["(-2,1)"]
    J --> K["(-2,0)"]
    K --> L["(-1,0)"]
    L --> M["(0,0)"]
    M --> N["(1,0)"]
    N --> O["(2,0)"]

If we visualize this path carefully, we can see it creates 2 closed regions!

The Naive Approach: Cycle Detection

My first instinct was to model this as a graph problem:

Create a node for each unique coordinate visited
Add edges between consecutive points in the path
Run DFS to detect cycles

Here’s what that looks like:

void dfsVisit(int u, const vector<vector<int>>& graph, 
              vector<int>& color, vector<int>& parent, 
              int& cycleCount) {
    color[u] = 1; // Gray - visiting
    
    for (int v : graph[u]) {
        if (color[v] == 0) { // Unvisited
            parent[v] = u;
            dfsVisit(v, graph, color, parent, cycleCount);
        } 
        else if (color[v] == 1 && parent[u] != v) {
            // Back edge found!
            cycleCount++;
        }
    }
    
    color[u] = 2; // Black - done
}

Problem: This approach is tricky! How do you avoid double-counting? How do you handle overlapping cycles? The relationship between back edges and actual closed regions isn’t straightforward.

The Elegant Solution: Euler’s Formula

Then comes the insight: the graph we’re building is planar (can be drawn on a plane without edge crossings). For such graphs, there’s a beautiful relationship:

[ V - E + F = 2 ]

Where:

$V$ = number of vertices (unique points)
$E$ = number of edges (unique connections)
$F$ = number of faces (including the outer infinite face)

Since we want only the bounded faces (closed regions), we subtract 1:

\[\text{Closed Regions} = F - 1 = E - V + 1\]

That’s it! Count vertices, count edges, apply the formula.

The Implementation

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

typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    string path;
    cin >> path;
    
    map<pii, int> points_index;
    points_index[{0, 0}] = 0;
    pii current = {0, 0};
    
    // Track unique edges
    set<pair<int,int>> edges;
    
    for (char step : path) {
        int i = points_index[current];
        
        // Move based on direction
        if (step == 'N') current.second++;
        else if (step == 'S') current.second--;
        else if (step == 'E') current.first++;
        else if (step == 'W') current.first--;
        
        // Add new point if needed
        if (!points_index.count(current)) {
            points_index[current] = points_index.size();
        }
        
        int j = points_index[current];
        
        // Add edge (normalized to avoid duplicates)
        edges.insert({min(i,j), max(i,j)});
    }
    
    int V = points_index.size();
    int E = edges.size();
    
    // Euler's formula: V - E + F = 2
    // Closed regions = F - 1 = E - V + 1
    int closed_regions = E - V + 1;
    
    cout << closed_regions << endl;
    
    return 0;
}

Time Complexity: $O(N \log V)$ where $N$ is the path length and $V$ is the number of unique vertices.

Space Complexity: $O(V + E)$

Why This Works

The key insight is that our path creates a connected planar graph:

Planar: No edges cross (they meet only at vertices)
Connected: You can reach any visited point from any other
Each edge traversed counts once: We use a set to track unique edges

Euler’s formula holds for any connected planar graph, making it perfect for this problem!

Interactive Visualization

Try it yourself! Enter a path string (using N, S, E, W) and see the closed regions:

Key Takeaways

Graph modeling is powerful: Converting the path to a graph opens up many algorithmic tools
Euler’s formula is elegant: A simple formula replaces complex cycle detection
Problem structure matters: Recognizing planarity was the key insight
Unique edges matter: Using a set to track edges prevents double-counting