All reachable problem ---island
https://leetcode.com/problems/number-of-islands
Island problem, 可以是一张图上，1）flood fill, 2) number of islands, 3) max area of the island
Question
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Clarification & Assumption
Graph Representation
vertex: 所有是“1” 的点
edge: four directions 为 “1” 的点
High Level
Problem definition
this is an all-reachable nodes problem
starting from every 1 vertex, traversing all connected element
What traversal algorithm?
DFS1, DFS2, DFS3(for each vertex, traverse all possible reachable vertex, by depth order, and make sure each vertex visited once)
BFS(for each vertex, traverse all possible reachable vertex, by level/breath order, and make sure each vertex visited once)
Middle Level
Graph representation?
Method 1: 完全分开
graph representation
vertex, int[][]
edge: four direction {-1, 0} {1, 0}, {0, -1}, {0, 1}
visited: boolean visited[][]
Method 2: 把visited单独出来
graph representation
Vertex: cell (int x, int y)
edge: four direction {-1, 0} {1, 0}, {0, -1}, {0, 1}:
visited: enum / boolean visited[][]
Method 3: 全部合在一起
Graph Representation, vertex & edge together
Vertex& Edge
Graph
Node {int x, int y, int value, boolean visited, Set<Vertex> neighb}
TC & SC
TC: O(|V| + |E|) = O (5mn), SC: O(mn)
Method 1 DFS
class Solution {
private static final int[][] DIRS = new int[][] {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
boolean[][] visited = new boolean[grid.length][grid[0].length];
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (visited[i][j] == false && grid[i][j] == '1') {
dfs(grid, i, j, visited);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int row, int col, boolean[][] visited) {
// // check visited
if (!isValid(grid, row, col) || visited[row][col] || grid[row][col] != '1') {
return;
}
// mark visited
visited[row][col] = true;
// visiting neighbor
for (int[] dir : DIRS) {
int neiX = row + dir[0];
int neiY = col + dir[1];
dfs(grid, neiX, neiY, visited);
}
}
private boolean isValid(char[][] grid, int row, int col) {
return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length;
}
}Method 1 BFS (& DFS)
class Solution {
class Cell {
int x;
int y;
public Cell (int x, int y) {
this.x = x;
this.y = y;
}
public int hashCode() {
return this.x * 31 + this.y;
}
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (this.getClass() != obj.getClass()) {
return false;
}
Cell that = (Cell)obj;
return this.x == that.x && this.y == that.y;
}
}
public int numIslands(char[][] grid) {
//sanity check
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
// build graph
// build visited check
boolean[][] visited = new boolean[grid.length][grid[0].length];
// bfs && dfs
// initial
// expand & generate
int[] count = new int[1];
for (int x = 0; x < grid.length; x++) {
for (int y = 0; y < grid[0].length; y++) {
if (grid[x][y] == '1' && visited[x][y] == false) {
Cell root = new Cell(x, y);
// bfs(grid, visited, root);
dfs(grid, visited, root);
count[0]++;
}
}
}
return count[0];
}
private void dfs (char[][] grid, boolean[][] visited, Cell root) {
if (!isValid(root.x, root.y, grid) || visited[root.x][root.y] || grid[root.x][root.y] != '1') {
return;
}
visited[root.x][root.y] = true;
for (int[] dir : DIRT) {
int neiX = root.x + dir[0];
int neiY = root.y + dir[1];
Cell nei = new Cell(neiX, neiY);
dfs(grid, visited, nei);
}
}
private void bfs (char[][] grid, boolean[][] visited, Cell root) {
Queue<Cell> queue = new ArrayDeque<>();
queue.offer(root);
visited[root.x][root.y] = true;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Cell cur = queue.poll();
for (int[] dir: DIRT) {
int neiX = cur.x + dir[0];
int neiY = cur.y + dir[1];
Cell nei = new Cell(neiX, neiY);
if (isValid(neiX, neiY, grid) && grid[neiX][neiY] == '1' && visited[neiX][neiY] == false) {
queue.offer(nei);
visited[nei.x][nei.y] = true;
}
}
}
}
}
private boolean isValid (int x, int y, char[][] grid) {
return x >= 0 && x < grid.length && y >=0 && y < grid[0].length;
}
private static final int[][] DIRT = new int[][] {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
}Method 3 BFS & DFS
class Solution {
class Vertex {
int x;
int y;
Set<Vertex> neighbors;
boolean visited;
char value;
public Vertex(int x, int y, char value) {
this.x = x;
this.y = y;
this.neighbors = new HashSet<>();
this.visited = false;
this.value = value;
}
@Override
public int hashCode() {
return this.x * 31 + this.y;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (this.getClass() != obj.getClass()) {
return false;
}
Vertex that = (Vertex) obj;
return this.x == that.x && this.y == that.y;
}
}
public int numIslands(char[][] grid) {
// sanity check
// buildGraph
Set<Vertex> graph = buildGraph(grid);
// traverse
int count = 0;
for (Vertex root: graph) {
if (isValid(root.x, root.y, grid) && root.value == '1' && root.visited != true) {
// bfs(root, graph, grid);
dfs(root, graph, grid);
count++;
}
}
return count;
}
private void bfs(Vertex root, Set<Vertex> graph, char[][] grid) {
Queue<Vertex> queue = new ArrayDeque<>();
queue.offer(root);
root.visited = true;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Vertex cur = queue.poll();
for (Vertex nei: cur.neighbors) {
if (isValid(nei.x, nei.y, grid) && nei.visited != true && nei.value == '1') {
queue.offer(nei);
nei.visited = true;
}
}
}
}
}
private void dfs(Vertex root, Set<Vertex> graph, char[][] grid) {
// base case
if (root.visited == true) {
return;
}
// cur step visited?
root.visited = true;
for (Vertex nei: root.neighbors) {
if (isValid(nei.x, nei.y, grid) && nei.value == '1') {
dfs(nei, graph, grid);
}
}
//
}
private Set<Vertex> buildGraph(char[][] grid) {
Set<Vertex> graph = new HashSet<>();
for (int x = 0; x < grid.length; x++) {
for (int y = 0; y < grid[0].length; y++) {
Vertex cur = new Vertex(x, y, grid[x][y]);
graph.add(cur);
}
}
for (Vertex vertex: graph) {
for (int[] dir: DIRT) {
int neiX = vertex.x + dir[0];
int neiY = vertex.y + dir[1];
if (isValid(neiX, neiY, grid)) {
for (Vertex nei: graph) {
if (nei.x == neiX && nei.y == neiY) {
vertex.neighbors.add(nei);
}
}
}
}
}
return graph;
}
private boolean isValid(int x, int y, char[][] grid) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}
private static final int[][] DIRT = new int[][]{{-1, 0},{1, 0}, {0,1}, {0, -1}};
} Method 2 DFS & BFS for maximum area of island
Last updated