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;
    }
}

All Problems

All Solutions