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;
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashSet;%0Aimport java.util.Set;%0A%0A
 /**%0A
@@ -153,88 +153,169 @@
     
-Set%3CString%3E zeroes = new HashSet%3C%3E();%0A        Set%3CString%3E ones = new HashSet%3C%3E()
+int maxRow = grid.length;%0A        int maxCol = maxRow %3E 0 ? grid%5B0%5D.length : 0;%0A        boolean%5B%5D%5B%5D visited = new boolean%5BmaxRow%5D%5BmaxCol%5D;%0A        int answer = 0
 ;%0A  
@@ -333,39 +333,28 @@
 int 
-row
+i
  = 0; 
-row %3C grid.length; row
+i %3C maxRow; i
 ++) 
@@ -380,44 +380,28 @@
 int 
-col
+j
  = 0; 
-col %3C grid%5Brow%5D.length; col
+j %3C maxCol; j
 ++) 
@@ -423,32 +423,28 @@
    if (grid%5B
-row%5D%5Bcol
+i%5D%5Bj
 %5D == '1') %7B%0A
@@ -467,115 +467,141 @@
     
-ones.add(buildKey(row, col));%0A                %7D else %7B%0A                    zeroes.add(buildKey(row, col));%0A
+if (!visited%5Bi%5D%5Bj%5D) %7B%0A                        answer++;%0A                        numIslands(grid, maxRow, maxCol, i, j, visited);%0A    
     
@@ -614,38 +614,32 @@
       %7D%0A        
-    %7D%0A
         %7D%0A      
@@ -644,271 +644,127 @@
     
-int result = 0;%0A        while (!ones.isEmpty()) %7B%0A            String%5B%5D str = ones.iterator().next().split(%22%5C%5C%7C%22);%0A            int row = Integer.parseInt(str%5B0%5D)
+    %7D%0A        %7D%0A        return answer
 ;%0A    
+%7D%0A%0A
     
-    int col = Integer.parseInt(str%5B1%5D);%0A            numIslands(grid, row, col, zeroes, ones);
+private static void numIslands(char%5B%5D%5B%5D grid, int maxRow, int maxCol,
 %0A   
@@ -776,26 +776,16 @@
     
-result++;%0A
         
 %7D%0A  
@@ -776,34 +776,32 @@
             
-%7D%0A
         
 return resul
@@ -792,228 +792,120 @@
     
-return result;%0A    %7D%0A%0A    private void numIslands(char%5B%5D%5B%5D grid, int row, int col, Set%3CString%3E zeroes, Set%3CString%3E ones) %7B%0A        String key = buildKey(row, col);%0A        if (!zeroes.contains(key) && !ones.contains(key)
+       int row, int col, boolean%5B%5D%5B%5D visited) %7B%0A        if (row %3C 0 %7C%7C row == maxRow %7C%7C col %3C 0 %7C%7C col == maxCol
 ) %7B%0A
@@ -942,24 +942,45 @@
         if (
+visited%5Brow%5D%5Bcol%5D %7C%7C 
 grid%5Brow%5D%5Bco
@@ -996,40 +996,8 @@
 ) %7B%0A
-            zeroes.remove(key);%0A
     
@@ -1034,24 +1034,32 @@
     
-ones.remove(key)
+visited%5Brow%5D%5Bcol%5D = true
 ;%0A  
@@ -1076,24 +1076,40 @@
 slands(grid,
+ maxRow, maxCol,
  row - 1, co
@@ -1107,36 +1107,31 @@
 w - 1, col, 
-zeroes, ones
+visited
 ); // up%0A   
@@ -1156,44 +1156,56 @@
 id, 
-row + 1, col, zeroes, ones
+maxRow, maxCol, row, col + 1, visited
 ); // 
-down
+right
 %0A   
@@ -1230,44 +1230,55 @@
 id, 
-row, col - 1, zeroes, ones
+maxRow, maxCol, row + 1, col, visited
 ); // 
-left
+down
 %0A   
@@ -1303,132 +1303,55 @@
 id, 
-row, col + 1, zeroes, ones); // right%0A    %7D%0A%0A    private String buildKey(int row, int col) %7B%0A        return row + %22%7C%22 + col;
+maxRow, maxCol, row, col - 1, visited); // left
 %0A   

Update problem 200