Regions Cut By Slashes

medium graph dfs matrix

Problem

Given an n×n grid of cells containing '/', '\\', or ' ', return the number of regions formed by the slashes.

Inputgrid = [" /","/ "]

Output2

Expand each cell into a 3×3 pixel block so slashes become walls, then DFS/flood-fill.

grid (rows by ';', spaces with '_')

def regionsBySlashes(grid):
    n = len(grid)
    g = [[0]*(3*n) for _ in range(3*n)]
    for r in range(n):
        for c in range(n):
            ch = grid[r][c]
            if ch == '/':
                g[3*r][3*c+2] = g[3*r+1][3*c+1] = g[3*r+2][3*c] = 1
            elif ch == '\\':
                g[3*r][3*c] = g[3*r+1][3*c+1] = g[3*r+2][3*c+2] = 1
    seen = [[False]*(3*n) for _ in range(3*n)]
    def dfs(r, c):
        if r < 0 or r >= 3*n or c < 0 or c >= 3*n or seen[r][c] or g[r][c]: return
        seen[r][c] = True
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
    count = 0
    for r in range(3*n):
        for c in range(3*n):
            if not seen[r][c] and not g[r][c]:
                dfs(r, c); count += 1
    return count

function regionsBySlashes(grid) {
  const n = grid.length;
  const g = Array.from({ length: 3 * n }, () => new Array(3 * n).fill(0));
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) {
    const ch = grid[r][c];
    if (ch === '/') { g[3*r][3*c+2] = g[3*r+1][3*c+1] = g[3*r+2][3*c] = 1; }
    else if (ch === '\\') { g[3*r][3*c] = g[3*r+1][3*c+1] = g[3*r+2][3*c+2] = 1; }
  }
  const seen = Array.from({ length: 3 * n }, () => new Array(3 * n).fill(false));
  function dfs(r, c) {
    if (r < 0 || r >= 3 * n || c < 0 || c >= 3 * n || seen[r][c] || g[r][c]) return;
    seen[r][c] = true;
    dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
  }
  let count = 0;
  for (let r = 0; r < 3 * n; r++) for (let c = 0; c < 3 * n; c++) {
    if (!seen[r][c] && !g[r][c]) { dfs(r, c); count++; }
  }
  return count;
}

class Solution {
    int n; int[][] g; boolean[][] seen;
    public int regionsBySlashes(String[] grid) {
        n = grid.length;
        g = new int[3 * n][3 * n];
        for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) {
            char ch = grid[r].charAt(c);
            if (ch == '/') { g[3*r][3*c+2] = g[3*r+1][3*c+1] = g[3*r+2][3*c] = 1; }
            else if (ch == '\\') { g[3*r][3*c] = g[3*r+1][3*c+1] = g[3*r+2][3*c+2] = 1; }
        }
        seen = new boolean[3 * n][3 * n];
        int count = 0;
        for (int r = 0; r < 3 * n; r++) for (int c = 0; c < 3 * n; c++)
            if (!seen[r][c] && g[r][c] == 0) { dfs(r, c); count++; }
        return count;
    }
    void dfs(int r, int c) {
        if (r < 0 || r >= 3 * n || c < 0 || c >= 3 * n || seen[r][c] || g[r][c] == 1) return;
        seen[r][c] = true;
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    }
}

int regionsBySlashes(vector<string>& grid) {
    int n = (int)grid.size();
    vector<vector<int>> g(3 * n, vector<int>(3 * n, 0));
    for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) {
        char ch = grid[r][c];
        if (ch == '/') g[3*r][3*c+2] = g[3*r+1][3*c+1] = g[3*r+2][3*c] = 1;
        else if (ch == '\\') g[3*r][3*c] = g[3*r+1][3*c+1] = g[3*r+2][3*c+2] = 1;
    }
    vector<vector<bool>> seen(3 * n, vector<bool>(3 * n, false));
    function<void(int, int)> dfs = [&](int r, int c) {
        if (r < 0 || r >= 3 * n || c < 0 || c >= 3 * n || seen[r][c] || g[r][c]) return;
        seen[r][c] = true;
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    };
    int count = 0;
    for (int r = 0; r < 3 * n; r++) for (int c = 0; c < 3 * n; c++)
        if (!seen[r][c] && !g[r][c]) { dfs(r, c); count++; }
    return count;
}

Explanation

The tricky part is that a / or \ cuts a single cell diagonally, which is awkward to count directly. The clever fix is to blow up every cell into a 3×3 block of pixels and draw the slash as a diagonal line of "wall" pixels. Once the slashes are just walls, counting regions becomes an ordinary flood-fill.

For each cell we mark wall pixels in a bigger grid g of size 3n × 3n. A / fills the anti-diagonal (top-right, center, bottom-left) and a \ fills the main diagonal (top-left, center, bottom-right). Empty cells leave all 9 pixels open.

Then we scan every pixel. Whenever we find an open pixel that hasn't been visited, we start a DFS that floods all connected open pixels (up, down, left, right), marking them seen. Each fresh flood is one new region, so we add 1 to count.

Example: grid = [" /", "/ "]. The two slashes form a continuous diagonal wall across the expanded grid, splitting the open pixels into two separate blobs, so the flood-fill runs twice and the answer is 2.

Expanding to 3×3 (not 2×2) matters: it guarantees diagonal walls actually touch and seal off regions instead of leaking through a corner.

Time: O(n²) Space: O(n²)