Leetcode 695. Max Area of Island"

发表于 更新于 分类于

本篇博客主要分析695. max area of island和733. Flood FillS，都可用深搜解决。

695. max area of island

题目

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

解法分析

思考及尝试解决无果后，根据标签，该问题属于depth-first-search，找到了采用递归函数解决的方案，很精简。

关键在于，处理边界问题，以及在取值计算1区域大小后置0。

实现如下: 

class Solution {
public:
    int AreaOfIsland(vector<vector<int>>& grid, int i, int j){
        if( i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == 1){
            grid[i][j] = 0;
            return 1 + AreaOfIsland(grid, i+1, j) + AreaOfIsland(grid, i-1, j) + AreaOfIsland(grid, i, j-1) + AreaOfIsland(grid, i, j+1);
        }
        return 0;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max_area = 0;
        int ysize=grid.size();
        int xsize=grid[0].size();
        for(int i = 0; i < ysize; i++)
            for(int j = 0; j < xsize; j++)
                if(grid[i][j] == 1)max_area = max(max_area, AreaOfIsland(grid, i, j));
        return max_area;
    }
};

733. Flood Fill

类似的问题还有很多，比如733. Flood Fill。

题目

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image.

To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Example 1:

Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: 
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.

Note:

  • The length of image and image[0] will be in the range [1, 50].
  • The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
  • The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

解法分析

同样的思路，实现如下：

class Solution {
public:
    void AreaOfSameColor(vector<vector<int>>& image,int sx,int sy,int color,int newColor)
    {
        //left,up,right,down;
        //(sx-1,sy),(sx,sy-1),(sx+1,sy),(sx,sy+1)  
        if(sx<0||sy<0||sx>=image[0].size()||sy>=image.size()||image[sy][sx]!=color)
            return;
        image[sy][sx]=newColor;
        AreaOfSameColor(image,sx-1,sy,color,newColor);
        AreaOfSameColor(image,sx,sy-1,color,newColor);
        AreaOfSameColor(image,sx+1,sy,color,newColor);
        AreaOfSameColor(image,sx,sy+1,color,newColor);
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        //sr:行,sc:列
        if(image[sr][sc]!=newColor)
            AreaOfSameColor(image,sc,sr,image[sr][sc],newColor);
        return image;
    }
};

重点也是在退出递归的边界条件上，另外，注意输入的新颜色与原色相同的特殊情况。

由以上可以看出递归代码明了，但是运行效率较差。