Welcome to Subscribe On Youtube

959. Regions Cut By Slashes

Description

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].length
  • 1 <= n <= 30
  • grid[i][j] is either '/', '\', or ' '.

Solutions

  • class Solution {
        private int[] p;
        private int size;
    
        public int regionsBySlashes(String[] grid) {
            int n = grid.length;
            size = n * n * 4;
            p = new int[size];
            for (int i = 0; i < p.length; ++i) {
                p[i] = i;
            }
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    int k = i * n + j;
                    if (i < n - 1) {
                        union(4 * k + 2, (k + n) * 4);
                    }
                    if (j < n - 1) {
                        union(4 * k + 1, (k + 1) * 4 + 3);
                    }
                    char v = grid[i].charAt(j);
                    if (v == '/') {
                        union(4 * k, 4 * k + 3);
                        union(4 * k + 1, 4 * k + 2);
                    } else if (v == '\\') {
                        union(4 * k, 4 * k + 1);
                        union(4 * k + 2, 4 * k + 3);
                    } else {
                        union(4 * k, 4 * k + 1);
                        union(4 * k + 1, 4 * k + 2);
                        union(4 * k + 2, 4 * k + 3);
                    }
                }
            }
            return size;
        }
    
        private int find(int x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }
    
        private void union(int a, int b) {
            int pa = find(a);
            int pb = find(b);
            if (pa == pb) {
                return;
            }
            p[pa] = pb;
            --size;
        }
    }
    
  • class Solution {
    public:
        vector<int> p;
        int size;
    
        int regionsBySlashes(vector<string>& grid) {
            int n = grid.size();
            size = n * n * 4;
            p.resize(size);
            for (int i = 0; i < size; ++i) p[i] = i;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    int k = i * n + j;
                    if (i < n - 1) merge(4 * k + 2, (k + n) * 4);
                    if (j < n - 1) merge(4 * k + 1, (k + 1) * 4 + 3);
                    char v = grid[i][j];
                    if (v == '/') {
                        merge(4 * k, 4 * k + 3);
                        merge(4 * k + 1, 4 * k + 2);
                    } else if (v == '\\') {
                        merge(4 * k, 4 * k + 1);
                        merge(4 * k + 2, 4 * k + 3);
                    } else {
                        merge(4 * k, 4 * k + 1);
                        merge(4 * k + 1, 4 * k + 2);
                        merge(4 * k + 2, 4 * k + 3);
                    }
                }
            }
            return size;
        }
    
        void merge(int a, int b) {
            int pa = find(a);
            int pb = find(b);
            if (pa == pb) return;
            p[pa] = pb;
            --size;
        }
    
        int find(int x) {
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        }
    };
    
  • class Solution:
        def regionsBySlashes(self, grid: List[str]) -> int:
            def find(x):
                if p[x] != x:
                    p[x] = find(p[x])
                return p[x]
    
            def union(a, b):
                pa, pb = find(a), find(b)
                if pa != pb:
                    p[pa] = pb
                    nonlocal size
                    size -= 1
    
            n = len(grid)
            size = n * n * 4
            p = list(range(size))
            for i, row in enumerate(grid):
                for j, v in enumerate(row):
                    k = i * n + j
                    if i < n - 1:
                        union(4 * k + 2, (k + n) * 4)
                    if j < n - 1:
                        union(4 * k + 1, (k + 1) * 4 + 3)
                    if v == '/':
                        union(4 * k, 4 * k + 3)
                        union(4 * k + 1, 4 * k + 2)
                    elif v == '\\':
                        union(4 * k, 4 * k + 1)
                        union(4 * k + 2, 4 * k + 3)
                    else:
                        union(4 * k, 4 * k + 1)
                        union(4 * k + 1, 4 * k + 2)
                        union(4 * k + 2, 4 * k + 3)
            return size
    
    
  • func regionsBySlashes(grid []string) int {
    	n := len(grid)
    	size := n * n * 4
    	p := make([]int, size)
    	for i := range p {
    		p[i] = i
    	}
    	var find func(x int) int
    	find = func(x int) int {
    		if p[x] != x {
    			p[x] = find(p[x])
    		}
    		return p[x]
    	}
    	union := func(a, b int) {
    		pa, pb := find(a), find(b)
    		if pa == pb {
    			return
    		}
    		p[pa] = pb
    		size--
    	}
    	for i, row := range grid {
    		for j, v := range row {
    			k := i*n + j
    			if i < n-1 {
    				union(4*k+2, (k+n)*4)
    			}
    			if j < n-1 {
    				union(4*k+1, (k+1)*4+3)
    			}
    			if v == '/' {
    				union(4*k, 4*k+3)
    				union(4*k+1, 4*k+2)
    			} else if v == '\\' {
    				union(4*k, 4*k+1)
    				union(4*k+2, 4*k+3)
    			} else {
    				union(4*k, 4*k+1)
    				union(4*k+1, 4*k+2)
    				union(4*k+2, 4*k+3)
    			}
    		}
    	}
    	return size
    }
    

All Problems

All Solutions