作者：cjaklxn_490 | 来源：互联网 | 2023-08-31 00:16
题目如下：解题思路：这个题目可以进行拆分成几个子问题。第一，求出island的数量，其实就是 200.NumberofIslands，这个很简单，DFS或者BFS都能搞定；第二，除
题目如下：
解题思路：这个题目可以进行拆分成几个子问题。第一，求出island的数量，其实就是 200. Number of Islands，这个很简单，DFS或者BFS都能搞定；第二，除了求出island的数量之外，还要求出每个island包括的1的数量，这个也不难，在DFS或者BFS的过程中计数即可；第三，遍历grid中所有的0，判断每个0的上下左右分别连接了几个不同的island，并将连接的所有island的所有1的数量求和，再加上本身的1（0变来的）即是这个0变成1可以得到的large island，最后，求出所有0的最大的large island即可。
代码如下：
class Solution(object):
def largestIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
for i in grid:
i.append('#')
i.insert(0,'#')
grid.append(['#' for i in grid[0]])
grid.insert(0,['#' for i in grid[0]])
visit = []
for i in grid:
visit.append([0 for x in i])
queue = []
l = [0]
area = 1
num = 1
for i in xrange(1,len(grid)):
for j in xrange(1,len(grid[i])):
if grid[i][j] == '#' or grid[i][j] == 0:
continue
if visit[i][j] != 0:
continue
queue.append((i,j,area))
visit[i][j] = area
while len(queue) > 0:
x,y,a = queue.pop(0) # a为island的编号，用来记录一个有几个island
if grid[x+1][y] == 1 and visit[x+1][y] == 0:
num += 1
queue.append((x+1,y,a))
visit[x + 1][y] = a
if grid[x-1][y] == 1 and visit[x-1][y] == 0:
num += 1
queue.append((x-1,y,a))
visit[x - 1][y] = a
if grid[x][y+1] == 1 and visit[x][y+1] == 0:
num += 1
queue.append((x,y+1,a))
visit[x][y + 1] = a
if grid[x][y-1] == 1 and visit[x][y-1] == 0:
num += 1
queue.append((x,y-1,a))
visit[x][y - 1] = a
area += 1
l.append(num) #l为每个island的1的数量
num = 1
res = 0
for i in l:
if res < i:
res = i
#print visit,l
for i in xrange(1,len(grid)):
for j in xrange(1,len(grid[i])):
if grid[i][j] == 0:
count = 1
al = []
if grid[i+1][j] == 1:
if visit[i+1][j] not in al:
count += l[visit[i+1][j]]
al.append(visit[i+1][j])
if grid[i-1][j] == 1:
if visit[i-1][j] not in al:
count += l[visit[i-1][j]]
al.append(visit[i-1][j])
if grid[i][j+1] == 1:
if visit[i][j+1] not in al:
count += l[visit[i][j+1]]
al.append(visit[i][j+1])
if grid[i][j-1] == 1:
if visit[i][j-1] not in al:
count += l[visit[i][j-1]]
al.append(visit[i][j-1])
if res < count:
res = count
return res
京公网安备 11010802041100号