Regions Cut By Slashes

Leetcode Problem:

• Regions Cut By Slashes

Summary

• Given an n x n grid represented as a string array, return the number of regions.

Approach

• The solution uses a 3D array to store the visited states of the grid cells
• It then uses a recursive DFS function to fill in the visited states of the neighboring cells
• The number of regions is incremented each time a new region is found.

Complexity

• O(n^2) where n is the size of the grid.

Explain

• The solution first converts the input grid into a 3D array where each cell represents a state in the DFS
• The states are defined as follows: - 0: not visited - 1: visited - 2: outside the grid The solution then uses a recursive DFS function to fill in the visited states of the neighboring cells
• If a cell is not visited and is outside the grid, it increments the number of regions and marks the cell as visited
• Finally, it returns the number of regions.

Solution Code:

class Solution {
public:
    int map[128][128];
    bool visited[128][128];
    int R, C;
    int ans = 0;
    void fill(int r, int c){
        if (r < 0 || r >= R || c < 0 || c >= C || map[r][c] == 1 || visited[r][c]){
            return;
        }
        visited[r][c] = true;
        fill(r + 1, c);
        fill(r, c + 1);
        fill(r - 1, c);
        fill(r, c - 1);
    }
    int regionsBySlashes(vector& grid) {
        R = grid.size();
        C = grid[0].length();
        for(int r = 0 ; r < R; r++){
            for(int c = 0; c < C; c++){
                if (grid[r][c] == '/'){
                    map[3*r][3*c+2] = 1;
                    map[3*r+1][3*c+1] = 1;
                    map[3*r+2][3*c] = 1;
                } else if (grid[r][c] == '\\'){
                    map[3*r][3*c] = 1;
                    map[3*r+1][3*c+1] = 1;
                    map[3*r+2][3*c+2] = 1;

                }
            }
        }
        R *= 3;
        C *= 3;
        for(int r = 0 ; r < R; r++){
            for(int c = 0 ; c < C; c++){
                if (map[r][c] == 0 && !visited[r][c]) {
                    fill(r, c);
                    ans++;
                }
            }
        }
        return ans;
    }
};