public int numIslands(char[][] grid) {

if (grid == null) return 0;

int n = grid.length;

if (n == 0) return 0;

int m = grid[0].length;

boolean[][] visited = new boolean[n][m];

int res = 0;

for (int i=0; i<n; i++) {

for (int j=0; j<m; j++) {

if (grid[i][j] == '1' && !visited[i][j]) {

numIslands(grid, visited, i, j, n, m);

res++;

}

}

}

return res;

}

private void numIslands(char[][] grid, boolean[][] visited, int i, int j, int n, int m) {

if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '0' || visited[i][j]) return;

visited[i][j] = true;

numIslands(grid, visited, i-1, j, n, m);

numIslands(grid, visited, i, j+1, n, m);

numIslands(grid, visited, i+1, j, n, m);

numIslands(grid, visited, i, j-1, n, m);

}

/**

public int numIslands2(char[][] grid) {

if (grid == null || grid.length == 0) {

return 0;

}

int nr = grid.length;

int nc = grid[0].length;

int num_islands = 0;

for (int r = 0; r < nr; ++r) {

for (int c = 0; c < nc; ++c) {

if (grid[r][c] == '1') {

++num_islands;

dfs(grid, r, c);

}

}

}

return num_islands;

}

void dfs(char[][] grid, int r, int c) {

int nr = grid.length;

int nc = grid[0].length;

if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {

return;

}

grid[r][c] = '0';

dfs(grid, r - 1, c);

dfs(grid, r + 1, c);

dfs(grid, r, c - 1);

dfs(grid, r, c + 1);

}

public int numIslands3(char[][] grid) {

if (grid == null) return 0;

int n = grid.length;

if (n == 0) return 0;

int m = grid[0].length;

boolean[][] visited = new boolean[n][m];

int res = 0;

for (int i=0; i<n; i++) {

for (int j=0; j<m; j++) {

if (grid[i][j] == '1' && !visited[i][j]) {

bfs(grid, visited, i, j, n, m);

res++;

}

}

}

return res;

}

private void bfs(char[][] grid, boolean[][] visited, int i, int j, int n, int m) {

Queue<Integer> q = new LinkedList<>();

q.add(i * m + j);

visited[i][j] = true;

while (!q.isEmpty()) {

int v = q.remove();

int ii = v / m;

int jj = v % m;

if (ii-1 >= 0 && grid[ii-1][jj] == '1' && !visited[ii-1][jj]) {

visited[ii-1][jj] = true;

q.add(v-m);

}

if (jj+1 < m && grid[ii][jj+1] == '1' && !visited[ii][jj+1]) {

visited[ii][jj+1] = true;

q.add(v+1);

}

if (ii+1 < n && grid[ii+1][jj] == '1' && !visited[ii+1][jj]) {

visited[ii+1][jj] = true;

q.add(v+m);

}

if (jj-1 >= 0 && grid[ii][jj-1] == '1' && !visited[ii][jj-1]) {

visited[ii][jj-1] = true;

q.add(v-1);

}

}

}

/**

class UnionFind {

int count; // # of connected components

int[] parent;

int[] rank;

public UnionFind(char[][] grid) { // for problem 200

count = 0;

int m = grid.length;

int n = grid[0].length;

parent = new int[m * n];

rank = new int[m * n];

for (int i = 0; i < m; ++i) {

for (int j = 0; j < n; ++j) {

int val = i * n + j;

if (grid[i][j] == '1') {

parent[val] = val;

++count;

}

rank[val] = 0;

}

}

}

public int find(int i) { // path compression

if (parent[i] != i) parent[i] = find(parent[i]);

return parent[i];

}

public void union(int x, int y) { // union with rank

int rootx = find(x);

int rooty = find(y);

if (rootx != rooty) {

if (rank[rootx] > rank[rooty]) {

parent[rooty] = rootx;

} else if (rank[rootx] < rank[rooty]) {

parent[rootx] = rooty;

} else {

parent[rooty] = rootx;

rank[rootx] += 1;

}

--count;

}

}

public int getCount() {

return count;

}

}

public int numIslands4(char[][] grid) {

if (grid == null || grid.length == 0) {

return 0;

}

int nr = grid.length;

int nc = grid[0].length;

int num_islands = 0;

UnionFind uf = new UnionFind(grid);

for (int r = 0; r < nr; ++r) {

for (int c = 0; c < nc; ++c) {

if (grid[r][c] == '1') {

int val = r * nc + c;

grid[r][c] = '0';

if (r - 1 >= 0 && grid[r-1][c] == '1') {

uf.union(val, val - nc);

}

if (r + 1 < nr && grid[r+1][c] == '1') {

uf.union(val, val + nc);

}

if (c - 1 >= 0 && grid[r][c-1] == '1') {

uf.union(val, val - 1);

}

if (c + 1 < nc && grid[r][c+1] == '1') {

uf.union(val, val + 1);

}

}

}

}

return uf.getCount();

}