Finding Disjoint Regions in a Grid (Rust)

2 min read 09-11-2024

Finding Disjoint Regions in a Grid (Rust)

Finding disjoint regions in a grid is a common problem in programming, especially in the context of pathfinding and spatial analysis. This article will explore how to implement a solution for this problem using the Rust programming language.

Understanding the Problem

A grid is typically represented as a 2D array where each cell can be occupied or unoccupied. The goal is to identify distinct regions that are connected, meaning you can traverse from one cell in a region to another using adjacent cells (horizontally or vertically).

Example of a Grid

Consider the following grid:

In this grid:

1 represents occupied cells.
0 represents unoccupied cells.

The grid consists of three disjoint regions made up of the 1s:

Region 1: Top-left corner
Region 2: Bottom-right single cell
Region 3: Bottom-left connected cells

Algorithm Overview

To find disjoint regions, we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the grid. The steps involved are:

Iterate through each cell in the grid.
When a 1 is encountered, initiate a search (DFS/BFS) to mark all connected 1s.
Keep a count of how many times we initiate a search, which will correspond to the number of disjoint regions.

Rust Implementation

Here’s how you can implement this approach in Rust:

fn find_disjoint_regions(grid: &Vec<Vec<i32>>) -> i32 {
    if grid.is_empty() {
        return 0;
    }

    let mut visited = vec![vec![false; grid[0].len()]; grid.len()];
    let mut region_count = 0;

    fn dfs(grid: &Vec<Vec<i32>>, visited: &mut Vec<Vec<bool>>, i: usize, j: usize) {
        // Check bounds
        if i >= grid.len() || j >= grid[0].len() || visited[i][j] || grid[i][j] == 0 {
            return;
        }
        
        // Mark the cell as visited
        visited[i][j] = true;

        // Explore neighbors (up, down, left, right)
        dfs(grid, visited, i.wrapping_sub(1), j); // up
        dfs(grid, visited, i + 1, j); // down
        dfs(grid, visited, i, j.wrapping_sub(1)); // left
        dfs(grid, visited, i, j + 1); // right
    }

    for i in 0..grid.len() {
        for j in 0..grid[0].len() {
            if grid[i][j] == 1 && !visited[i][j] {
                dfs(grid, &mut visited, i, j);
                region_count += 1; // Increment region count
            }
        }
    }

    region_count
}

fn main() {
    let grid = vec![
        vec![1, 1, 0, 0],
        vec![1, 0, 0, 1],
        vec![0, 0, 0, 1],
        vec![0, 1, 1, 1],
    ];

    let regions = find_disjoint_regions(&grid);
    println!("Number of disjoint regions: {}", regions);
}

Explanation of the Code

Grid Initialization: The grid is initialized as a vector of vectors representing the 2D grid.
Visited Tracking: A visited matrix is used to keep track of cells that have already been counted as part of a region.
DFS Function: A recursive function that marks all connected cells as visited.
Counting Regions: Every time a new unvisited 1 is found, we call the dfs function and increment our region count.

Conclusion

This Rust implementation provides an efficient way to find disjoint regions in a grid using a DFS approach. You can further enhance the algorithm by adding features like counting the size of each region or handling larger grids with more complex rules. The flexibility of Rust's ownership model and its performance characteristics make it an excellent choice for such tasks.