0695._Max_Area_of_Island.md

695. Max Area of Island

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/max-area-of-island/description/

内容描述

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.

解题方案

思路 1

对于每一个点我们不停的dfs，然后每次碰到一个点是1我们就将当前area加1，然后把这个点变成0，每一次都更新我们的res，最终返回res

class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or len(grid) == 0:
            return 0
        m = len(grid)
        n = len(grid[0]) if m else 0
        
        def dfs(i, j, area):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
                return area
            else:
                grid[i][j] = 0
                area += 1
            for x, y in ([(i, j+1), (i, j-1), (i+1, j), (i-1, j)]):
                area = dfs(x, y, area)
            return area 

        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                area = dfs(i, j, 0)
                res = max(res, area)
        return res

Follow up:

If we still want the max area of the island, but if one land is surrrounded all by land, then it should not be part of our area, how can we solve it?

比如：

1 0 0 1 1 1
1 0 0 1 1 1
0 0 0 0 1 1

这个我们要返回的是7而不是8，因为坐标为(1,4)的点被陆地包围，所以我们不算他的面积

大概思路就是并查集，然后各大岛屿的坐标集合遍历一遍看看有没有没有点完全被包围，有的话就面积减1，然后最后算出来， 参考leetcode 200 和 leetcode 305

def find(x, uf):
    while x != uf[x]:
        uf[x] = uf[uf[x]]
        x = uf[x]
    return uf[x]

class Solution(object):
    uf, idx = {}, 1
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])



        def sink(i, j):
            if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
                self.uf[(i,j)] = self.uf[self.idx] = self.idx
                grid[i][j] = '0'
                for x, y in [(i, j+1), (i, j-1), (i+1, j), (i-1, j)]:
                    if (x,y) in self.uf:
                        root = find(self.uf[(x,y)], self.uf)
                        self.uf[root] = self.idx
                self.idx += 1
                map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1))

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                sink(i, j)
        return self.uf

grid = [["1","1","1","1","0"],["1","1","1","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
grid1 = [["1","1","1","1","0"],["1","1","1","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
# print(Solution().numIslands(grid))

uf = Solution().numIslands(grid)
print(uf)

islands = {}
for key in uf.keys():
    if type(key).__name__ != 'int':
        if find(key, uf) not in islands:
            islands[find(key, uf)] = [key]
        else:
            islands[find(key, uf)].append(key)
print(islands)

print(grid)
max_aera = -float('inf')
for key in islands.keys():
    aera = len(islands[key])
    for i, j in islands[key]:
        tmp = 0
        for x, y in [(i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)]:
            if 0 <= x < len(grid1) and 0 <= y < len(grid1[0]) and grid1[x][y] == '1':
                tmp += 1
        if tmp == 4:
            aera -= 1
    max_aera = max(max_aera, aera)
print(max_aera)