959. Regions Cut By Slashes

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space. These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as "\\".)

Return the number of regions.

Example 1:

Input:
[
  " /",
  "/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:

Example 2:

Input:
[
  " /",
  "  "
]
Output: 1
Explanation: The 2x2 grid is as follows:

Example 3:

Input:
[
  "\\/",
  "/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:

Example 4:

Input:
[
  "/\\",
  "\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:

Example 5:

Input:
[
  "//",
  "/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:

Note:

1. 1 <= grid.length == grid[0].length <= 30
2. grid[i][j] is either '/', '\', or ' '.

subject In an N x N grid consisting of 1 x 1 squares, each 1 x 1 square is composed of /, or spaces. These characters divide the box into some common areas. (Note that the backslash character is escaped, so \ is denoted by ). Number of return areas.

Thought: Reference to God votrubac Of solution . Expand the grid represented by the string expression to three times, as shown in the following figure (the picture is from votrubac, intrusion and deletion). The lower right is an enlarged image, and the black part represents the original/or. The final result is obtained by dfs of the enlarged graph.

Engineering Code Download

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        vector<vector<int>> g(n*3, vector<int>(n*3));
        
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(grid[i][j] == '/')
                    g[i*3][j*3+2] = g[i*3+1][j*3+1] = g[i*3+2][j*3] = 1;
                else if(grid[i][j] == '\\')
                    g[i*3][j*3] = g[i*3+1][j*3+1] = g[i*3+2][j*3+2] = 1;
            }
        }
        
        int res = 0;
        for(int i = 0; i < n*3; ++i){
            for(int j = 0; j < n*3; ++j){
                if(g[i][j] == 0){
                    dfs(g, i, j);
                    res += 1;
                }
            }
        }

        return res;
    }
private:
    void dfs(vector<vector<int>>& g, int i, int j){
        if(i < 0 || i >= g.size() || j < 0 || j >= g.size() || g[i][j] == 1)
            return;
        g[i][j] = 1;
        
        dfs(g, i+1, j);        
        dfs(g, i-1, j);
        dfs(g, i, j+1);
        dfs(g, i, j-1);
    }
};