Given an m x n 2d grid 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.
/*
use flood fill, use dfs to traverse all island, and mark vistied
time complexity: O(n*m), space complexity: O(1), n is grid's height, m is grid's width
*/
class Solution {
private int n; //grid's height
private int m; //grid's width
public int numIslands(char[][] grid) {
n = grid.length;
if (n == 0) return 0;
m = grid[0].length;
int count = 0;
// loop grid[][]
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') { //if touch the land, do dfs traverser
dfs(grid, i, j);
count++; //find island, count++
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
// terminator
// out of bound or it's water
if (i < 0 || j < 0 || i >= n || j >=m || grid[i][j] == '0') return;
//drill down
// an islan to be sinked, visited, island becomes water
grid[i][j] = '0';
// traverse all surrouding area
dfs(grid, i+1, j);
dfs(grid, i, j+1);
dfs(grid, i-1, j);
dfs(grid, i, j-1);
}
}
加上座標的話, 更清楚
public static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int n; // graph's height
private int m; // width
public int numIslands(char[][] grid) {
n = grid.length;
if (n == 0) return 0;
m = grid[0].length;
int count = 0; // the count of island
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') { // an island's start
dfs(grid, i, j); //run dfs, run through an island
count++; // count of island++
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != '1') return;
grid[i][j] = '0'; // mark visited
for (int d[] : directions) {
dfs(grid, i + d[0], j + d[1]); // toward different directions...
}
}
use visited, dont modify origin grid value(no flood fill)
因為在某些題目是不能改值的 , 這時候還是要用 visited 來標記走過了
使用 visited,
class Solution {
private int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int res = 0;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
dfs(grid, i, j, visited);
res++;
}
}
}
return res;
}
private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
if (!inArea(grid, i, j) || visited[i][j] || grid[i][j] == '0') {
return;
}
visited[i][j] = true;
for (int[] dir : dirs) {
dfs(grid, i + dir[0], j + dir[1], visited);
}
}
private boolean inArea(char[][] grid, int i, int j) {
return i >= 0 && i < grid.length && j >=0 && j < grid[0].length;
}
}