My Java Solution


  • 0
    L
    public int numIslands(char[][] grid) {
        if (null==grid||grid.length==0) {
    		return 0;
    	}
    	int num=0;
        for (int i = 0; i < grid.length; i++) {
    		for (int j = 0; j < grid[0].length; j++) {
    			if (grid[i][j]=='1') {
    				if (!hasNeighbor(grid, i, j)) {
    					num++;
    				}
    				grid[i][j]='x';
    				Stack<Integer[]> stack=new Stack<Integer[]>();
    				stack.push(new Integer[]{i,j});
    				while(stack.size()>0){
    					Integer[] index=stack.pop();
    					Integer[] neighbor=findNeighborNotSet(grid, index[0], index[1]);
    					if (null!=neighbor) {
    						stack.push(index);
    						stack.push(neighbor);
    					}
    				}
    			}
    		}
    	}
        return num;
    }
        public Integer[] findNeighborNotSet(char[][] grid, int x,int y){
    	if ((x-1>=0)&&grid[x-1][y]=='1') {
    		grid[x-1][y]='x';
    		return new Integer[]{x-1,y};
    	}else if (y-1>=0&&grid[x][y-1]=='1') {
    		grid[x][y-1]='x';
    		return new Integer[]{x,y-1};
    	}else if (x+1<=grid.length-1&&grid[x+1][y]=='1') {
    		grid[x+1][y]='x';
    		return new Integer[]{x+1,y};
    	}else if (y+1<=grid[0].length-1&&grid[x][y+1]=='1') {
    		grid[x][y+1]='x';
    		return new Integer[]{x,y+1};
    	}
    	return null;
    }
    
    public boolean hasNeighbor(char[][] grid, int x,int y){
    	if ((x-1>=0)&&grid[x-1][y]=='x') {
    		return true;
    	}else if (y-1>=0&&grid[x][y-1]=='x') {
    		return true;
    	}else if (x+1<=grid.length-1&&grid[x+1][y]=='x') {
    		return true;
    	}else if (y+1<=grid[0].length-1&&grid[x][y+1]=='x') {
    		return true;
    	}
    	return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.