Problem
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' '.
Solution
/**
* @param {string[]} grid
* @return {number}
*/
var regionsBySlashes = function(grid) {
var matrix = Array(3 * grid.length).fill(0).map(() => Array(3 * grid.length).fill(0));
for (var i = 0; i < grid.length; i++) {
for (var j = 0; j < grid[i].length; j++) {
if (grid[i][j] === '\\') {
matrix[i * 3][j * 3] = 1;
matrix[i * 3 + 1][j * 3 + 1] = 1;
matrix[i * 3 + 2][j * 3 + 2] = 1;
} else if (grid[i][j] === '/') {
matrix[i * 3][j * 3 + 2] = 1;
matrix[i * 3 + 1][j * 3 + 1] = 1;
matrix[i * 3 + 2][j * 3] = 1;
}
}
}
var res = 0;
for (var i = 0; i < matrix.length; i++) {
for (var j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] === 0) {
visitAndMark(matrix, i, j, ++res);
}
}
}
return res;
};
var visitAndMark = function(matrix, i, j, num) {
matrix[i][j] = num;
matrix[i][j + 1] === 0 && visitAndMark(matrix, i, j + 1, num);
matrix[i][j - 1] === 0 && visitAndMark(matrix, i, j - 1, num);
matrix[i + 1]?.[j] === 0 && visitAndMark(matrix, i + 1, j, num);
matrix[i - 1]?.[j] === 0 && visitAndMark(matrix, i - 1, j, num);
};
Explain:
nope.
Complexity:
- Time complexity : O(n ^ 2).
- Space complexity : O(n ^ 2).