Formatted question description: https://leetcode.ca/all/959.html

959. Regions Cut By Slashes (Medium)

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 ' '.

Companies: Uber

Related Topics: Depth-first Search, Union Find, Graph

Solution 1.

For a square, if it’s split by a \ or /, the left region (the one touches the left border) is denoted as 0, the right region is denoted as 1.

// OJ: https://leetcode.com/problems/regions-cut-by-slashes/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
private:
    unordered_set<int> seen;
    int ans = 0, N;
    int hash(int i, int j, int pos) {
        return i + j  * 100 + pos * 10000;
    }
    void insert(queue<int> &q, int h) {
        if (seen.find(h) != seen.end()) return;
        q.push(h);
        seen.insert(h);
    }
    int bfs(vector<string>& grid, int i, int j, int pos) {
        int h = hash(i, j, pos);
        if (seen.find(h) != seen.end()) return 0;
        seen.insert(h);
        queue<int> q;
        q.push(h);
        while (q.size()) {
            int val = q.front();
            q.pop();
            i = val % 100;
            j = val / 100 % 100;
            pos = val / 10000;
            if (grid[i][j] == '\\') {
                if (pos == 0) {
                    if (j - 1 >= 0) insert(q, hash(i, j - 1, 1));
                    if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0));
                } else {
                    if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1));
                    if (j + 1 < N) insert(q, hash(i, j + 1, 0));
                }
            } else if (grid[i][j] == '/') {
                if (pos == 0) {
                    if (j - 1 >= 0) insert(q, hash(i, j - 1, 1));
                    if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1));
                } else {
                    if (j + 1 < N) insert(q, hash(i, j + 1, 0));
                    if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0));
                }
            } else {
                insert(q, hash(i, j, 1 - pos));
                if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1));
                if (j + 1 < N) insert(q, hash(i, j + 1, 0));
                if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0));
                if (j - 1 >= 0) insert(q, hash(i, j - 1, 1));
            }
        }
        return 1;
    }
public:
    int regionsBySlashes(vector<string>& grid) {
        N = grid.size();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                ans += bfs(grid, i, j, 0);
                ans += bfs(grid, i, j, 1);
            }
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/regions-cut-by-slashes/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
    const int dirs[4][2] = { {0, 1}, {0,-1}, {1, 0}, {-1, 0} };
    int N;
    void dfs(vector<vector<int>> &g, int x, int y, int color) {
        if (x < 0 || x >= N || y < 0 || y >= N || g[x][y]) return;
        g[x][y] = color;
        for (auto &dir : dirs) dfs(g, x + dir[0], y + dir[1], color);
    }
public:
    int regionsBySlashes(vector<string>& grid) {
        N = grid.size();
        vector<vector<int>> g(3 * N, vector<int>(3 * N, 0));
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == '/') g[3 * i][3 * j + 2] = g[3 * i + 1][3 * j + 1] = g[3 * i + 2][3 * j] = 1;
                else if (grid[i][j] == '\\') g[3 * i][3 * j] = g[3 * i + 1][3 * j + 1] = g[3 * i + 2][3 * j + 2] = 1;
            }
        }
        N *= 3;
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                 if (!g[i][j]) dfs(g, i, j, ++ans + 1);
            }
        }
        return ans;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/regions-cut-by-slashes/
// Time: O(N^2)
// Space: O(N^2)
#define TO(d) dfs(grid, g, x + dirs[d][0], y + dirs[d][1], d, color)
class Solution {
    int N;
    void setLeftColor(vector<vector<int>> &g, int x, int y, int color) {
        g[x][y] += color * 100;
    }
    void setRightColor(vector<vector<int>> &g, int x, int y, int color) {
        g[x][y] += color;
    }
    int getLeftColor(vector<vector<int>> &g, int x, int y) {
        return g[x][y] / 100;
    }
    int getRightColor(vector<vector<int>> &g, int x, int y) {
        return g[x][y] % 100;
    }
    int dirs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
    // 0 U, 1 R, 2 D, 3 L
    void dfs(vector<string>& grid, vector<vector<int>> &g, int x, int y, int d, int color) {
        if (x < 0 || x >= N || y < 0 || y >= N) return;
        if (grid[x][y] == ' ') {
            if (g[x][y]) return;
            g[x][y] = color;
            for (int i = 0; i < 4; ++i) TO(i);
        } else if (grid[x][y] == '/') {
            if (!getLeftColor(g, x, y) && (d == 2 || d == 1)) {
                setLeftColor(g, x, y, color);
                TO(0);
                TO(3);
            }
            if (!getRightColor(g, x, y) && (d == 0 || d == 3)) {
                setRightColor(g, x, y, color);
                TO(1);
                TO(2);
            }
        } else {
            if (!getLeftColor(g, x, y) && (d == 1 || d == 0)) {
               setLeftColor(g, x, y, color);
                TO(2);
                TO(3);
            }
            if (!getRightColor(g, x, y) && (d == 2 || d == 3)) {
                setRightColor(g, x, y, color);
                TO(0);
                TO(1);
            }
        }
    }
public:
    int regionsBySlashes(vector<string>& grid) {
        N = grid.size();
        int color = 0;
        vector<vector<int>> g(N, vector<int>(N, 0));
        for (int x = 0; x < N; ++x) {
            for (int y = 0; y < N; ++y) {
                if (grid[x][y] == ' ') {
                    if (!g[x][y]) dfs(grid, g, x, y, 0, ++color);
                }
                else if (grid[x][y] == '/') {
                    if (!getLeftColor(g, x, y)) {
                        ++color;
                        dfs(grid, g, x, y, 1, color);
                        dfs(grid, g, x, y, 2, color);
                    }
                    if (!getRightColor(g, x, y)) {
                        ++color;
                        dfs(grid, g, x, y, 0, color);
                        dfs(grid, g, x, y, 3, color);
                    }
                } else {
                    if (!getLeftColor(g, x, y)) {
                        ++color;
                        dfs(grid, g, x, y, 0, color);
                        dfs(grid, g, x, y, 1, color);
                    }
                    if (!getRightColor(g, x, y)) {
                        ++color;
                        dfs(grid, g, x, y, 2, color);
                        dfs(grid, g, x, y, 3, color);
                    }
                }
            }
        }
        return color;
    }
};

Java

  • class Solution {
        public int regionsBySlashes(String[] grid) {
            int length = grid.length;
            int[][][] regions = new int[length][length][4];
            int regionCount = 1;
            int remain = length * length * 4;
            Queue<int[]> queue = new LinkedList<int[]>();
            char topLeft = grid[0].charAt(0);
            if (topLeft == ' ') {
                for (int i = 0; i < 4; i++) {
                    regions[0][0][i] = regionCount;
                    remain--;
                }
                for (int i = 2; i < 4; i++)
                    queue.offer(new int[]{0, 0, i});
            } else if (topLeft == '/') {
                for (int i = 0; i < 2; i++) {
                    regions[0][0][i] = regionCount;
                    remain--;
                }
                regionCount++;
                for (int i = 2; i < 4; i++) {
                    regions[0][0][i] = regionCount;
                    remain--;
                    queue.offer(new int[]{0, 0, i});
                }
            } else {
                for (int i = 0; i < 4; i += 2) {
                    regions[0][0][i] = regionCount;
                    remain--;
                    queue.offer(new int[]{0, 0, i});
                }
            }
            while (remain > 0) {
                while (!queue.isEmpty()) {
                    int[] subcell = queue.poll();
                    int row = subcell[0], column = subcell[1], subcellNum = subcell[2];
                    char c = grid[row].charAt(column);
                    if (c == ' ') {
                        for (int i = 0; i < 4; i++) {
                            if (regions[row][column][i] == 0) {
                                regions[row][column][i] = regionCount;
                                remain--;
                                queue.offer(new int[]{row, column, i});
                            }
                        }
                    } else if (c == '/') {
                        int num1 = subcellNum % 2 == 0 ? subcellNum : subcellNum - 1;
                        int num2 = num1 + 1;
                        for (int i = num1; i <= num2; i++) {
                            if (regions[row][column][i] == 0) {
                                regions[row][column][i] = regionCount;
                                remain--;
                                queue.offer(new int[]{row, column, i});
                            }
                        }
                    } else {
                        int num1 = subcellNum < 2 ? subcellNum : subcellNum - 2;
                        int num2 = num1 + 2;
                        for (int i = num1; i <= num2; i += 2) {
                            if (regions[row][column][i] == 0) {
                                regions[row][column][i] = regionCount;
                                remain--;
                                queue.offer(new int[]{row, column, i});
                            }
                        }
                    }
                    int[] adjacentSubcell = getAdjacentSubcell(row, column, subcellNum);
                    int nextRow = adjacentSubcell[0], nextColumn = adjacentSubcell[1], nextSubcellNum = adjacentSubcell[2];
                    if (nextRow >= 0 && nextRow < length && nextColumn >= 0 && nextColumn < length && regions[nextRow][nextColumn][nextSubcellNum] == 0) {
                        regions[nextRow][nextColumn][nextSubcellNum] = regionCount;
                        remain--;
                        queue.offer(adjacentSubcell);
                    }
                }
                if (remain == 0)
                    break;
                regionCount++;
                outer:
                for (int i = 0; i < length; i++) {
                    for (int j = 0; j < length; j++) {
                        for (int k = 0; k < 4; k++) {
                            if (regions[i][j][k] == 0) {
                                regions[i][j][k] = regionCount;
                                remain--;
                                queue.offer(new int[]{i, j, k});
                                break outer;
                            }
                        }
                    }
                }
            }
            return regionCount;
        }
    
        public int[] getAdjacentSubcell(int row, int column, int subcellNum) {
            int[] adjacentSubcell = {row, column, subcellNum};
            switch (subcellNum) {
                case 0:
                    adjacentSubcell[0]--;
                    break;
                case 1:
                    adjacentSubcell[1]--;
                    break;
                case 2:
                    adjacentSubcell[1]++;
                    break;
                case 3:
                    adjacentSubcell[0]++;
                    break;
                default:
            }
            adjacentSubcell[2] = 3 - adjacentSubcell[2];
            return adjacentSubcell;
        }
    }
    
  • // OJ: https://leetcode.com/problems/regions-cut-by-slashes/
    // Time: O(N^2)
    // Space: O(N^2)
    class Solution {
    private:
        unordered_set<int> seen;
        int ans = 0, N;
        int hash(int i, int j, int pos) {
            return i + j  * 100 + pos * 10000;
        }
        void insert(queue<int> &q, int h) {
            if (seen.find(h) != seen.end()) return;
            q.push(h);
            seen.insert(h);
        }
        int bfs(vector<string>& grid, int i, int j, int pos) {
            int h = hash(i, j, pos);
            if (seen.find(h) != seen.end()) return 0;
            seen.insert(h);
            queue<int> q;
            q.push(h);
            while (q.size()) {
                int val = q.front();
                q.pop();
                i = val % 100;
                j = val / 100 % 100;
                pos = val / 10000;
                if (grid[i][j] == '\\') {
                    if (pos == 0) {
                        if (j - 1 >= 0) insert(q, hash(i, j - 1, 1));
                        if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0));
                    } else {
                        if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1));
                        if (j + 1 < N) insert(q, hash(i, j + 1, 0));
                    }
                } else if (grid[i][j] == '/') {
                    if (pos == 0) {
                        if (j - 1 >= 0) insert(q, hash(i, j - 1, 1));
                        if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1));
                    } else {
                        if (j + 1 < N) insert(q, hash(i, j + 1, 0));
                        if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0));
                    }
                } else {
                    insert(q, hash(i, j, 1 - pos));
                    if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1));
                    if (j + 1 < N) insert(q, hash(i, j + 1, 0));
                    if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0));
                    if (j - 1 >= 0) insert(q, hash(i, j - 1, 1));
                }
            }
            return 1;
        }
    public:
        int regionsBySlashes(vector<string>& grid) {
            N = grid.size();
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) {
                    ans += bfs(grid, i, j, 0);
                    ans += bfs(grid, i, j, 1);
                }
            }
            return ans;
        }
    };
    
  • class Solution(object):
        def regionsBySlashes(self, grid):
            """
            :type grid: List[str]
            :rtype: int
            """
            self.N = len(grid)
            m_ = range(self.N * self.N * 4)
            self.count = self.N * self.N * 4
            for row in range(self.N):
                line = grid[row]
                for col in range(self.N):
                    w = line[col]
                    if row > 0:
                        self.union(m_, self.position(row - 1, col, 2), self.position(row, col, 0))
                    if col > 0:
                        self.union(m_, self.position(row, col - 1, 1), self.position(row, col, 3))
                    if w != '/':
                        self.union(m_, self.position(row, col, 0), self.position(row, col, 1))
                        self.union(m_, self.position(row, col, 3), self.position(row, col, 2))
                    if w != '\\':
                        self.union(m_, self.position(row, col, 0), self.position(row, col, 3))
                        self.union(m_, self.position(row, col, 1), self.position(row, col, 2))
            return self.count
    
        def find(self, m_, a):
            if m_[a] == a:
                return a
            return self.find(m_, m_[a])
        
        def union(self, m_, a, b):
            pa = self.find(m_, a)
            pb = self.find(m_, b)
            if (pa == pb):
                return
            m_[pa] = pb
            self.count -= 1
        
        def position(self, r, c, i):
            return (r * self.N + c) * 4 + i
    

All Problems

All Solutions