package leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/number-of-islands/
 */
public class Problem200 {
    public int numIslands(char[][] grid) {
        Set<String> zeroes = new HashSet<>();
        Set<String> ones = new HashSet<>();
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[row].length; col++) {
                if (grid[row][col] == '1') {
                    ones.add(buildKey(row, col));
                } else {
                    zeroes.add(buildKey(row, col));
                }
            }
        }
        int result = 0;
        while (!ones.isEmpty()) {
            String[] str = ones.iterator().next().split("\\|");
            int row = Integer.parseInt(str[0]);
            int col = Integer.parseInt(str[1]);
            numIslands(grid, row, col, zeroes, ones);
            result++;
        }
        return result;
    }

    private void numIslands(char[][] grid, int row, int col, Set<String> zeroes, Set<String> ones) {
        String key = buildKey(row, col);
        if (!zeroes.contains(key) && !ones.contains(key)) {
            return;
        }
        if (grid[row][col] == '0') {
            zeroes.remove(key);
            return;
        }
        ones.remove(key);
        numIslands(grid, row - 1, col, zeroes, ones); // up
        numIslands(grid, row + 1, col, zeroes, ones); // down
        numIslands(grid, row, col - 1, zeroes, ones); // left
        numIslands(grid, row, col + 1, zeroes, ones); // right
    }

    private String buildKey(int row, int col) {
        return row + "|" + col;
    }
}

package leetcode;

/**
 * https://leetcode.com/problems/number-of-islands/
 */
public class Problem200 {
    public int numIslands(char[][] grid) {
        int maxRow = grid.length;
        int maxCol = maxRow > 0 ? grid[0].length : 0;
        boolean[][] visited = new boolean[maxRow][maxCol];
        int answer = 0;
        for (int i = 0; i < maxRow; i++) {
            for (int j = 0; j < maxCol; j++) {
                if (grid[i][j] == '1') {
                    if (!visited[i][j]) {
                        answer++;
                        numIslands(grid, maxRow, maxCol, i, j, visited);
                    }
                }
            }
        }
        return answer;
    }

    private static void numIslands(char[][] grid, int maxRow, int maxCol,
                                   int row, int col, boolean[][] visited) {
        if (row < 0 || row == maxRow || col < 0 || col == maxCol) {
            return;
        }
        if (visited[row][col] || grid[row][col] == '0') {
            return;
        }
        visited[row][col] = true;
        numIslands(grid, maxRow, maxCol, row - 1, col, visited); // up
        numIslands(grid, maxRow, maxCol, row, col + 1, visited); // right
        numIslands(grid, maxRow, maxCol, row + 1, col, visited); // down
        numIslands(grid, maxRow, maxCol, row, col - 1, visited); // left
    }
}

Update problem 200