Number of Islands

200. Number of Islands

def numIslands(self, grid: List[List[str]]) -> int:
    if not grid: return 0
    
    self.grid = grid
    count = 0
    self.m, self.n = len(grid), len(grid[0])
    for i in range(self.m):
        for j in range(self.n):
            if grid[i][j] == '1':
                self.helper(i, j)
                count+=1
    return count

def helper(self, i, j):
    self.grid[i][j] = '0'
    
    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        x = i + dx
        y = j + dy
        
        if 0 <= x < self.m and 0 <= y < self.n and self.grid[x][y] == '1':
            self.helper(x, y)

305 Number of Islands II

A 2d grid initials with zeroes. Given a list of positions to operate, count the number of islands after each addLand operation. Example:

Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]] Output: [1,1,2,3]

• Use UnionFind, no group in the beginning, init all father node as -1

• Check if neighbor has initiated(father[x]>0)

class UnionFind{
    int count;
    int[] father = null;
    int[] size = null;

    public UnionFind(int n){
        this.count = 0;
        father = new int[n];
        size = new int[n];

        for(int i=0; i<n; i++){
            father[i] = -1;
        }
    }

    public void addIsland(int x){
        father[x] = x;
        size[x] = 1;
        count++;
    }

    public int find(int x){
        if(father[x] != x) father[x] = find(father[x]);
        return father[x];
    }

    public void union(int x, int y){
        int x_root = find(x);
        int y_root = find(y);

        if(x_root != y_root){
            if(size[x_root] > size[y_root]){
                father[y_root] = x_root;
                size[x_root] += size[y_root];
            }else{
                father[x_root] = y_root;
                size[y_root] += size[x_root];
            }
            count--;
        }
    }

    public boolean isValid(int x){
        // System.out.println(x);
        return father[x] >= 0;
    }

    public int getCount(){
        return count;
    }
}
public List<Integer> numIslands2(int m, int n, int[][] positions) {
    UnionFind uf = new UnionFind(m*n);
    List<Integer> ans = new ArrayList<>();
    for(int[] p: positions){
        int num = p[0]*n + p[1];
        uf.addIsland(num);
        if(p[0]>0 && uf.isValid(num-n)) uf.union(num, num-n);
        if(p[0]<m-1 && uf.isValid(num+n)) uf.union(num, num+n);
        if(p[1]>0 && uf.isValid(num-1)){
            // System.out.println("here");
            uf.union(num, num-1);
        }
        if(p[1]<n-1 && uf.isValid(num+1)) uf.union(num, num+1);
        ans.add(uf.getCount());
    }
    return ans;
}

694. Number of Distinct Islands

Given a non-empty 2D array grid of 0's and 1's,Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

• Shift the nodes to original trigger point

• Use Set to compare the islands

def numDistinctIslands(self, grid: List[List[int]]) -> int:
    self.m, self.n = len(grid), len(grid[0])
    self.grid = grid
    counts = set()
    
    for i in range(self.m):
        for j in range(self.n):
            if grid[i][j] == 1:
                count = set()
                self.helper(i, j, i, j, count)
                counts.add(frozenset(count))
    return len(counts)

def helper(self, i, j, i0, j0, count):
    count.add((i-i0, j-j0))
    self.grid[i][j] = 0
    
    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        x = i + dx
        y = j + dy
        
        if 0 <= x < self.m and 0 <= y < self.n and self.grid[x][y] == 1:
            self.helper(x, y, i0, j0, count)

463. Island Perimeter

Only has 1 island

"""
遇到 1, 判斷上下左右是不是島嶼的一部份 減去邊長
"""
def islandPerimeter(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    count = 0
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                line = 4
                if i != 0 and grid[i-1][j]:
                    line -= 1
                if i != m-1 and grid[i+1][j]:
                    line -= 1
                if j != 0 and grid[i][j-1]:
                    line -= 1
                if j != n-1 and grid[i][j+1]:
                    line -= 1
                count += line
    return count

Image Matching

/**
 *  Given two 2-D grid, find out the number of region that if grid1 can cover grid2
 *  For example:
 *
 *  101  101
 *  101  100
 *  100  100  return 2 cuz second region in grid1 covers the region in grid2
 *
 *  Thought:
 *  1. dfs from grid2 to search the boundary of each region.
 *  2. In the process of dfs, check if the boundary goes beyond grid1
 */

public class imageMatching {
    private int image(int[][] grid1, int[][] grid2){
        int count=0;
        int m = grid2.length;
        int n = grid2[0].length;

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid2[i][j] == 1 && dfs(grid1, grid2, i, j)) count++;
            }
        }
        return count;
    }

    private boolean dfs(int[][] grid1, int[][] grid2, int i, int j){
        int m = grid2.length;
        int n = grid2[0].length;
        grid2[i][j] = 0;
        boolean up = true, down = true, left = true, right = true;
        if(i>0 && grid2[i-1][j] == 1) up = dfs(grid1, grid2, i-1, j);
        if(i<m-1 && grid2[i+1][j] == 1) down = dfs(grid1, grid2, i+1, j);
        if(j>0 && grid2[i][j-1] == 1) left = dfs(grid1, grid2, i, j-1);
        if(j<n-1 && grid2[i][j+1] == 1) right = dfs(grid1, grid2, i, j+1);

        return grid1[i][j] == 1 && left && right && up && down;
    }

Image Matching 2

/**
 *  Given two 2-D grid, find out the number of identical region of 2 grids
 *  For example:
 *
 *  101  101
 *  101  101
 *  100  101  return 1
 *
 *  Thought:
 *  1. grid1 and grid2 make a OR operation, dfs from OrMap to search the boundary of each region.
 *  2. In the process of dfs, check if grid1 and grid2 the same
 */


static int countMatches(List<String> grid1, List<String> grid2) {
    int count = 0;
    int m = grid1.size();
    int n = grid1.get(0).length();
    int[][] g1 = new int[m][n];
    int[][] g2 = new int[m][n];
    int[][] orMap = new int[m][n];

    // create g1 and g2
    for(int i=0; i<m; i++){
        char[] str1 = grid1.get(i).toCharArray();
        char[] str2 = grid2.get(i).toCharArray();
        for(int j=0; j<n; j++){
            g1[i][j] = str1[j] - '0';
            g2[i][j] = str2[j] - '0';
        }
    }
    // create orMap
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            orMap[i][j] = g1[i][j] | g2[i][j];
        }
    }

    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(orMap[i][j] == 1 && dfs(g1, g2, orMap, i, j)) count++;
        }
    }
    return count;
}

private static boolean dfs(int[][] g1, int[][] g2, int[][] orMap, int i, int j){
    int m = orMap.length;
    int n = orMap[0].length;
    orMap[i][j] = 0;
    boolean up = true, down = true, left = true, right = true;
    if(i>0 && orMap[i-1][j] == 1) up = dfs(g1, g2, orMap, i-1, j);
    if(i<m-1 && orMap[i+1][j] == 1) down = dfs(g1, g2, orMap, i+1, j);
    if(j>0 && orMap[i][j-1] == 1) left = dfs(g1, g2, orMap, i, j-1);
    if(j<n-1 && orMap[i][j+1] == 1) right = dfs(g1, g2, orMap, i, j+1);

    return g1[i][j]==1 && g2[i][j]==1 && up && down && left && right;
}