959. Regions Cut By Slashes LeetCode Solution

In this guide, you will get 959. Regions Cut By Slashes LeetCode Solution with the best time and space complexity. The solution to Regions Cut By Slashes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Regions Cut By Slashes solution in C++
Regions Cut By Slashes solution in Java
Regions Cut By Slashes solution in Python
Additional Resources

959. Regions Cut By Slashes LeetCode Solution image

Problem Statement of Regions Cut By Slashes

An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a ‘/’, ‘\’, or blank space ‘ ‘. These characters divide the square into contiguous regions.
Given the grid grid represented as a string array, return the number of regions.
Note that backslash characters are escaped, so a ‘\’ is represented as ‘\\’.

Example 1:

Input: grid = [” /”,”/ “]
Output: 2

Example 2:

Input: grid = [” /”,” “]
Output: 1

Example 3:

Input: grid = [“/\\”,”\\/”]
Output: 5
Explanation: Recall that because \ characters are escaped, “\\/” refers to \/, and “/\\” refers to /\.

Constraints:

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

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

959. Regions Cut By Slashes LeetCode Solution in C++

class Solution {
 public:
  int regionsBySlashes(vector<string>& grid) {
    const int n = grid.size();
    // G := upscaled grid
    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] = 1;
          g[i * 3 + 1][j * 3 + 1] = 1;
          g[i * 3 + 2][j * 3] = 1;
        } else if (grid[i][j] == '\\') {
          g[i * 3][j * 3] = 1;
          g[i * 3 + 1][j * 3 + 1] = 1;
          g[i * 3 + 2][j * 3 + 2] = 1;
        }

    int ans = 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);
          ++ans;
        }

    return ans;
  }

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

    g[i][j] = 2;  // Mark 2 as visited.
    dfs(g, i + 1, j);
    dfs(g, i - 1, j);
    dfs(g, i, j + 1);
    dfs(g, i, j - 1);
  }
};
/* code provided by PROGIEZ */

959. Regions Cut By Slashes LeetCode Solution in Java

class Solution {
  public int regionsBySlashes(String[] grid) {
    final int n = grid.length;
    // G := upscaled grid
    int[][] g = new int[n * 3][n * 3];

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i].charAt(j) == '/') {
          g[i * 3][j * 3 + 2] = 1;
          g[i * 3 + 1][j * 3 + 1] = 1;
          g[i * 3 + 2][j * 3] = 1;
        } else if (grid[i].charAt(j) == '\\') {
          g[i * 3][j * 3] = 1;
          g[i * 3 + 1][j * 3 + 1] = 1;
          g[i * 3 + 2][j * 3 + 2] = 1;
        }

    int ans = 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);
          ++ans;
        }

    return ans;
  }

  private void dfs(int[][] g, int i, int j) {
    if (i < 0 || i == g.length || j < 0 || j == g[0].length)
      return;
    if (g[i][j] != 0)
      return;

    g[i][j] = 2; // Mark 2 as visited.
    dfs(g, i + 1, j);
    dfs(g, i - 1, j);
    dfs(g, i, j + 1);
    dfs(g, i, j - 1);
  }
}
// code provided by PROGIEZ