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].length1 <= n <= 30grid[i][j]is either'/','\', or' '.
Approach 01:
-
C++
-
Python
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
const int gridSize = grid.size();
// upscaledGrid is a 3x size grid to represent slashes more precisely
vector<vector<int>> upscaledGrid(gridSize * 3, vector<int>(gridSize * 3));
// Fill the upscaled grid based on the slashes in the original grid
for (int row = 0; row < gridSize; ++row) {
for (int col = 0; col < gridSize; ++col) {
if (grid[row][col] == '/') {
upscaledGrid[row * 3][col * 3 + 2] = 1;
upscaledGrid[row * 3 + 1][col * 3 + 1] = 1;
upscaledGrid[row * 3 + 2][col * 3] = 1;
} else if (grid[row][col] == '\\') {
upscaledGrid[row * 3][col * 3] = 1;
upscaledGrid[row * 3 + 1][col * 3 + 1] = 1;
upscaledGrid[row * 3 + 2][col * 3 + 2] = 1;
}
}
}
int regionCount = 0;
// Perform DFS to find connected regions
for (int row = 0; row < gridSize * 3; ++row) {
for (int col = 0; col < gridSize * 3; ++col) {
if (upscaledGrid[row][col] == 0) {
dfs(upscaledGrid, row, col);
++regionCount;
}
}
}
return regionCount;
}
private:
void dfs(vector<vector<int>>& upscaledGrid, int row, int col) {
// Boundary and visited checks
if (row < 0 || row == upscaledGrid.size() || col < 0 || col == upscaledGrid[0].size()) {
return;
}
if (upscaledGrid[row][col] != 0) {
return;
}
upscaledGrid[row][col] = 2; // Mark as visited
dfs(upscaledGrid, row + 1, col); // Down
dfs(upscaledGrid, row - 1, col); // Up
dfs(upscaledGrid, row, col + 1); // Right
dfs(upscaledGrid, row, col - 1); // Left
}
};
class Solution:
def regionsBySlashes(self, grid):
gridSize = len(grid)
# upscaledGrid is a 3x size grid to represent slashes more precisely
upscaledGrid = [[0] * (gridSize * 3) for _ in range(gridSize * 3)]
# Fill the upscaled grid based on the slashes in the original grid
for row in range(gridSize):
for col in range(gridSize):
if grid[row][col] == '/':
upscaledGrid[row * 3][col * 3 + 2] = 1
upscaledGrid[row * 3 + 1][col * 3 + 1] = 1
upscaledGrid[row * 3 + 2][col * 3] = 1
elif grid[row][col] == '\\':
upscaledGrid[row * 3][col * 3] = 1
upscaledGrid[row * 3 + 1][col * 3 + 1] = 1
upscaledGrid[row * 3 + 2][col * 3 + 2] = 1
regionCount = 0
# Perform DFS to find connected regions
for row in range(gridSize * 3):
for col in range(gridSize * 3):
if upscaledGrid[row][col] == 0:
self.dfs(upscaledGrid, row, col)
regionCount += 1
return regionCount
def dfs(self, upscaledGrid, row, col):
# Boundary and visited checks
if row < 0 or row == len(upscaledGrid) or col < 0 or col == len(upscaledGrid[0]):
return
if upscaledGrid[row][col] != 0:
return
upscaledGrid[row][col] = 2 # Mark as visited
self.dfs(upscaledGrid, row + 1, col) # Down
self.dfs(upscaledGrid, row - 1, col) # Up
self.dfs(upscaledGrid, row, col + 1) # Right
self.dfs(upscaledGrid, row, col - 1) # Left
Time Complexity
- Upscaling the Grid:
The upscaled grid is created by iterating over each cell in the original grid, and based on whether there is a
`/`or`\`, specific cells in the upscaled grid are marked. This step involves iterating through all cells in the original grid, leading to a time complexity of \( O(n^2) \), where \( n \) is the size of the original grid (i.e., \( n \times n \) grid). - DFS for Region Counting:
The DFS algorithm is then run on each cell of the upscaled grid. In the worst case, DFS visits every cell in the upscaled grid. The upscaled grid is of size \( 3n \times 3n \), so this step has a time complexity of \( O((3n)^2) = O(n^2) \).
- Overall Time Complexity:
Both the upscaling and DFS steps have a time complexity of \( O(n^2) \), so the overall time complexity is \( O(n^2) \).
Space Complexity
- Upscaled Grid:
The algorithm uses an upscaled grid that is \( 3n \times 3n \) in size to more precisely represent slashes. This requires \( O((3n)^2) = O(n^2) \) space.
- DFS Stack Space:
The DFS recursion uses additional space for the call stack. In the worst case, the stack could be as deep as the number of cells in the upscaled grid, leading to a space complexity of \( O(n^2) \).
- Overall Space Complexity:
The overall space complexity is dominated by the upscaled grid, so it is \( O(n^2) \).