C solution using region growing


  • 0
    int** regionGrow(int** grid, int gridRowSize, int gridColSize, int i, int j, int tagRegion) {
        grid[i][j] = tagRegion;
        if (i-1 >= 0 && grid[i-1][j] == 1) {
            grid = regionGrow(grid, gridRowSize, gridColSize, i-1, j, tagRegion);
        }
        if (i+1 < gridRowSize && grid[i+1][j] == 1) {
            grid = regionGrow(grid, gridRowSize, gridColSize, i+1, j, tagRegion);
        }
        if (j-1 >= 0 && grid[i][j-1] == 1) {
            grid = regionGrow(grid, gridRowSize, gridColSize, i, j-1, tagRegion);
        }
        if (j+1 < gridColSize && grid[i][j+1] == 1) {
            grid = regionGrow(grid, gridRowSize, gridColSize, i, j+1, tagRegion);
        }
        return grid;
    }
    
    int maxAreaOfIsland(int** grid, int gridRowSize, int gridColSize) {
        int i, j;
        int *area, max = 0;
        int tagRegion = 2;
    
        for (i=0;i<gridRowSize;i++) {
            for (j=0;j<gridColSize;j++) {
                if (grid[i][j] == 1) {
                    grid = regionGrow(grid, gridRowSize, gridColSize, i, j, tagRegion);
                    tagRegion++;
                }
            }
        }
    
        area = malloc(sizeof(int)*(tagRegion-2));
        
        for (i=0; i < tagRegion-2; i++) {
            area[i] = 0;
        }
        
        for (i=0;i<gridRowSize;i++) {
            for (j=0;j<gridColSize;j++) {
                if (grid[i][j] > 0) {
                    area[grid[i][j] - 2] += 1;
                }
            }
        }
            
        for (i=0; i < tagRegion-2; i++) {
            if (area[i] > max) {
                max = area[i];
            }
        }
        
        free(area);
        
        return max;
    }
    

Log in to reply
 

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