# Number of Islands

## 200. Number of Islands

```python
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)

```java
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

```python
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

```python
"""
遇到 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

```java
/**
 *  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

```java
/**
 *  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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/bfs/number-of-thousand-island.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.