class Solution {

    /**
     * @param String[][] $grid
     * @return Integer
     */
    function numIslands($grid) {
        $count = 0;

        for ($i=0; $i<count($grid); $i++) {
            for ($j=0; $j<count($grid[$i]); $j++) {
                if ($grid[$i][$j] == "1") {
                    $count++;
                    // zero out rest of 1s
                    $this->zeroOut($grid, $i, $j);
                }
            }
        }

        return $count;
    }

    function zeroOut(&$grid, $i, $j) {
        if ($i<0 || $i>=count($grid) || $j<0 || $j>=count($grid[$i]) || $grid[$i][$j] == "0")
            return;

        $grid[$i][$j] = "0";

        $this->zeroOut($grid, $i-1, $j);
        $this->zeroOut($grid, $i+1, $j);
        $this->zeroOut($grid, $i, $j-1);
        $this->zeroOut($grid, $i, $j+1);
    }
}