diff options
-rw-r--r-- | regions_cut_by_slashes.c | 56 | ||||
-rw-r--r-- | regions_cut_by_slashes.py | 47 |
2 files changed, 103 insertions, 0 deletions
diff --git a/regions_cut_by_slashes.c b/regions_cut_by_slashes.c new file mode 100644 index 0000000..6bef879 --- /dev/null +++ b/regions_cut_by_slashes.c @@ -0,0 +1,56 @@ +// 959. Regions Cut By Slashes +#include "leetcode.h" + +/* + * an 'n * n' grid is composed of 1 * 1 squares where each 1 * 1 square consists + * of a '/' or '\' 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. + */ + +void dfs(int **grid, int x, int y, int n) { + if (x < 0 || x >= 3 * n || y < 0 || y >= 3 * n || grid[x][y]) + return; + grid[x][y] = -1; + dfs(grid, x + 1, y, n); + dfs(grid, x - 1, y, n); + dfs(grid, x, y + 1, n); + dfs(grid, x, y - 1, n); +} + +int regionsBySlashes(char **grid, int gridSize) { + int expand_size = gridSize * 3, ans = 0; + int **expand = (int **)malloc(expand_size * sizeof(int *)); + for (int i = 0; i < expand_size; i++) { + expand[i] = (int *)malloc(expand_size * sizeof(int)); + memset(expand[i], 0, expand_size * sizeof(int)); + } + for (int i = 0; i < gridSize; i++) + for (int j = 0; j < gridSize; j++) + if (grid[i][j] == '/') { + expand[i * 3][j * 3 + 2] = 1; + expand[i * 3 + 2][j * 3 + 1] = 1; + expand[i * 3 + 2][j * 3] = 1; + } else if (grid[i][j] == '\\') { + expand[i * 3][j * 3] = 1; + expand[i * 3 + 2][j * 3 + 1] = 1; + expand[i * 3 + 2][j * 3 + 2] = 1; + } + for (int i = 0; i < expand_size; i++) + for (int j = 0; j < expand_size; j++) + if (!expand[i][j]) { + dfs(expand, i, j, gridSize); + ans++; + } + for (int i = 0; i < expand_size; i++) + free(expand[i]); + free(expand); + return ans; +} + +int main() { + char *g1[] = {" /", "/ "}, *g2[] = {" /", " "}, *g3[] = {"/\\", "\\/"}; + printf("%d\n", regionsBySlashes((char **)g1, ARRAY_SIZE(g1))); // expect: 2 + printf("%d\n", regionsBySlashes((char **)g2, ARRAY_SIZE(g2))); // expect: 1 + printf("%d\n", regionsBySlashes((char **)g3, ARRAY_SIZE(g3))); // expect: 5 +} diff --git a/regions_cut_by_slashes.py b/regions_cut_by_slashes.py new file mode 100644 index 0000000..c25a08e --- /dev/null +++ b/regions_cut_by_slashes.py @@ -0,0 +1,47 @@ +# 959. Regions Cut By Slashes + +""" +an 'n * n' grid is composed of 1 * 1 squares where each 1 * 1 square consists +of a '/' or '\' 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. +""" + + +class Solution(object): + def regionsBySlashes(self, grid): + """ + :type grid: List[str] + :rtype: int + """ + n = {} + + def find(x): + n.setdefault(x, x) + if x != n[x]: + n[x] = find(n[x]) + return n[x] + + def union(x, y): + n[find(x)] = find(y) + + for i in range(len(grid)): + for j in range(len(grid)): + if i: + union((i - 1, j, 2), (i, j, 0)) + if j: + union((i, j - 1, 1), (i, j, 3)) + if grid[i][j] != "/": + union((i, j, 0), (i, j, 1)) + union((i, j, 2), (i, j, 3)) + if grid[i][j] != "\\": + union((i, j, 3), (i, j, 0)) + union((i, j, 1), (i, j, 2)) + return len(set(map(find, n))) + + +if __name__ == "__main__": + obj = Solution() + print(obj.regionsBySlashes(grid=[" /", "/ "])) + print(obj.regionsBySlashes(grid=[" /", " "])) + print(obj.regionsBySlashes(grid=["/\\", "\\/"])) |