Given a non-empty 2D arraygridof 0's and 1's, anislandis a group of1'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.)
. 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 givengriddoes not exceed 50.
dfs
每次dfs是一个连通块，计算每块里面多少个。 这里visited直接设置Matrix = -1
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
n,m = len(grid),len(grid[0])
d = [-1, 0, 1, 0, -1]
def dfs(i,j):
nonlocal cnt
if grid[i][j] != 1:
return
grid[i][j] = -1
for x, y in [(i + d[k], j + d[k + 1]) for k in range(4)]:
if 0 <= x < n and 0 <= y < m and grid[x][y] == 1:
cnt += 1
dfs(x,y)
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
cnt = 1
dfs(i,j)
res = max(res,cnt)
return res
dfs II
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
n,m = len(grid),len(grid[0])
d = [-1,0,1,0,-1]
def dfs(x,y):
grid[x][y] = -1
cnt = 1
for nx,ny in [(x+d[i],y+d[i+1]) for i in range(4)]:
if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
cnt += dfs(nx,ny)
return cnt
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
temp = dfs(i,j)
res = max(res,temp)
return res
BFS
visited在出栈时候设置就一直错，非要在入栈时候设置才行，不知道为什么
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
n,m = len(grid),len(grid[0])
d = [-1, 0, 1, 0, -1]
def bfs(a,b)->int:
cnt = 1
q = [(a,b)]
grid[a][b] = -1
while q:
i,j = q.pop(0)
for x, y in [(i + d[k], j + d[k + 1]) for k in range(4)]:
if 0 <= x < n and 0 <= y < m and grid[x][y] == 1:
cnt += 1
q.append((x,y))
grid[x][y] = -1
return cnt
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
cnt = bfs(i,j)
res = max(res,cnt)
return res
Union find
用了size和rank,记得最后取size的时候再find一次，很重要！！！
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
n,m = len(grid),len(grid[0])
f = list(range(n*m))
rank = [0]*(n*m)
size = [1]*(n*m)
d = [-1, 0, 1, 0, -1]
def find(x):
if f[x] == x:
return x
f[x] = find(f[x])
return f[x]
def union(x,y):
# if x== y:return False
fx,fy = find(x),find(y)
if fx == fy:
return size[fx]
if rank[fy] > rank[fx]:
f[fx] = fy
size[fy] += size[fx]
return size[fy]
elif rank[fy] < rank[fx]:
f[fy] = fx
size[fx] += size[fy]
return size[fx]
else:
f[fy] = fx
rank[fx] += 1
size[fx] += size[fy]
return size[fx]
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
temp = size[find(i*m+j)] #再find一次
for x, y in [(i + d[k], j + d[k + 1]) for k in range(4)]:
if 0 <= x < n and 0 <= y < m and grid[x][y] == 1 :
temp = max(res,union(x*m+y,i*m+j))
res = max(res,temp)
return res