首页 > 试题广场 >

岛屿数量

[编程题]岛屿数量

热度指数：120846 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右）判断岛屿个数。

例如：

输入

[

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

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

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

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

[0,0,1,1,1]

]

对应的输出为3

(注：存储的01数据其实是字符'0','1')

示例1

输入

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

输出

示例2

输入

[[0]]

输出

示例3

输入

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

输出

备注:

01矩阵范围<=200*200

算法知识视频讲解

Python 3

lun__

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
############ 求所有岛屿的面积，之后对面积列表求 len() ############# 
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        row = len(grid) 
        col = len(grid[0]) 
        
        if row == 0&nbs***bsp;col == 0 : 
            return 0 
        
        areasum = [] 
        for i in range(row): 
            for j in range(col): 
                res = 0
                que = [] 
                if grid[i][j] == "1": 
                    res += 1 
                    grid[i][j] = "0" 
                    que.append((i,j)) 
                    
                    while que: 
                        cur_i, cur_j = que.pop(0) 
                        
                        for x, y in [(0,1), (0,-1), (1,0), (-1,0)]: 
                            temp_i = cur_i + x 
                            temp_j = cur_j + y 
                            
                            if 0<=temp_i<row and 0<=temp_j<col and grid[temp_i][temp_j]=="1": 
                                res += 1 
                                grid[temp_i][temp_j] = "0" 
                                que.append((temp_i, temp_j))
                    areasum.append(res) ## 找出所有岛屿的面积和，然后求 len 
        print(areasum) 
        return len(areasum) 
###############################
################ 采用计数操作，计算岛屿面积 #################### 
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        row = len(grid) 
        col = len(grid[0]) 
        
        if row == 0&nbs***bsp;col == 0 : 
            return 0
        que = [] 
        count = 0 
        for i in range(row): 
            for j in range(col): 
                
                if grid[i][j] == "1": 
                    grid[i][j] = "0" 
                    que.append((i,j))
                    
                    while que: 
                        cur_i, cur_j = que.pop(0) 
                        
                        for x, y in [(0,1), (0,-1), (1,0), (-1,0)]: 
                            temp_i = cur_i + x 
                            temp_j = cur_j + y 
                            
                            if 0<=temp_i<row and 0<=temp_j<col and grid[temp_i][temp_j] == "1": 
                                grid[temp_i][temp_j] = "0"  
                                que.append((temp_i, temp_j))
                    count += 1 
        return count

发表于 2022-08-30 15:33:28 回复(0)

Python 3

蓝鲸与风

class Solution:
    #深度优先遍历与i，j相邻的所有1
    def dfs(self, grid:List[List[str]], i:int, j:int):
        m=len(grid)#返回行数
        n=len(grid[0])#返回列数
        grid[i][j]='0'#每个1的位置只访问1次，防止岛屿重复计数
        #避免重复统计，找到之后就置成0
        #后续四个方向遍历,遍历每个岛屿的路径，走有1的路径
        if i-1>=0 and grid[i-1][j] =='1':
            self.dfs(grid,i-1,j)
        if i+1<m and grid[i+1][j] =='1':
            self.dfs(grid,i+1,j)
        if j-1>=0 and grid[i][j-1] =='1':
            self.dfs(grid,i,j-1)
        if j+1<n and grid[i][j+1] =='1':
            self.dfs(grid,i,j+1)
    def solve(self , grid: List[List[str]]) -> int:
        m=len(grid)#返回行数
        count =0
        if m ==0:#空矩阵，必定没有岛屿
            return count
        n=len(grid[0])#返回列数
        for i in range(m):
            for j in range(n):
                if grid[i][j] =='1':#因为，每次找到一条路径，也就是找到岛屿，就置为0，
                    #出现1，必定是新的岛屿
                    count +=1
                    self.dfs(grid,i,j)         
        return count

发表于 2022-08-20 21:59:43 回复(0)

Python 3

Vivimore

遍历每个格子，寻找孤立的岛屿，如若找到则将该岛屿炸沉（将1变成0），继续遍历格子寻找岛屿

class Solution:
    def dfs(self, grid, i, j):
        n = len(grid)
        m = len(grid[0])
        grid[i][j] = '0'
        if i - 1 >= 0 and grid[i-1][j] == '1':
            self.dfs(grid, i-1, j)
        if i + 1 < n and grid[i+1][j] == '1':
            self.dfs(grid, i+1, j)
        if j - 1 >= 0 and grid[i][j-1] == '1':
            self.dfs(grid, i, j-1)
        if j + 1 < m and grid[i][j+1] == '1':
            self.dfs(grid, i, j+1)

    def solve(self , grid: List[List[str]]) -> int:
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])
        count = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    count += 1
                    self.dfs(grid, i, j)
        return count

发表于 2022-05-19 21:28:35 回复(0)

Python 3

我是赵同学

dfs

class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        self.grid = grid
        self.h = len(grid)
        self.w = len(grid[0])
        self.ans = 0
        for i in range(self.h):
            for j in range(self.w):
                if self.grid[i][j]=='1':
                    self.ans += 1
                    self.DFS(i, j)         
        return self.ans  
    def DFS(self,i,j):
        if i< 0 or j< 0 or i == self.h or j == self.w or self.grid[i][j]=='0':
            return        
        self.grid[i][j]='0'
        self.DFS(i+1, j)
        self.DFS(i-1, j)
        self.DFS(i, j+1)
        self.DFS(i, j-1)

发表于 2022-04-11 23:13:38 回复(0)

Python 3

阿珍阿珍

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        row = len(grid)
        cols = len(grid[0])
        ans = 0
        for i in range(row):
            for j in range(cols):
                ans = max(self.dfs(grid, i, j), ans)
        return ans
    
    def dfs(self, grid, r, c):
        if r<0&nbs***bsp;c<0&nbs***bsp;r==len(grid)&nbs***bsp;c==len(grid[0])&nbs***bsp;grid[r][c]!=1:
            return 0
        grid[r][c]=0
        count = 1
        for ii,jj in [[1,0], [-1,0], [0,1], [0,-1]]:
            r1, c1 = r + ii, c + jj
            count += self.dfs(grid, r1, c1)
        return count

为什么这段代码在leetcode上面运行正确，这里确实错误？

发表于 2022-04-01 13:47:15 回复(1)

Python 3

牛客964040622号

我的代码没问题，但是在牛客网里面的得到的答案总是跟预期不一致。

发表于 2022-03-31 09:35:44 回复(0)

Python 3

牛客296365098号

遍历，生长

class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        
        visit = [[0 for _ in grid[0]] for _ in grid]
        
        cntIsland = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1' and not visit[i][j]:
                    self.bfs(grid, visit, i, j)
                    cntIsland += 1
        return cntIsland
                    
                    
    def bfs(self, grid, visit, i, j):
        if grid[i][j] == '1':
            visit[i][j] = 1
            if i+1 < len(grid) and not visit[i+1][j]:
                self.bfs(grid, visit, i+1, j)
            if i-1 >= 0 and not visit[i-1][j]:
                self.bfs(grid, visit, i-1, j)
            if j+1 < len(grid[0]) and not visit[i][j+1]:
                self.bfs(grid, visit, i, j+1)
            if j-1 >= 0 and not visit[i][j-1]:
                self.bfs(grid, visit, i, j-1)
        return

发表于 2022-03-07 22:48:58 回复(0)

Python 3

Joy_9

class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        m=len(grid)
        n=len(grid[0])
        count=0
        def dfs(r,c):
            if (r>m-1&nbs***bsp;r<0)&nbs***bsp;(c>n-1&nbs***bsp;c<0):
                return False
            elif grid[r][c]!=str(1):
                return False
            grid[r][c]=2
            dfs(r-1,c)
            dfs(r+1,c)
            dfs(r,c-1)
            dfs(r,c+1)
        for i in range(m):
            for j in range(n):
                if grid[i][j]==str(1):
                    dfs(i,j)
                    count+=1
        return count

发表于 2022-01-02 03:25:40 回复(0)

Python 3

牛客896772195号

这。。。能不能讲讲清楚0和1是数还是字符啊，垃圾牛客

发表于 2021-12-30 10:58:23 回复(0)

Python 3

牛客38477449号

class Solution:
    def solve(self , grid ):
        # write code here
        if grid == []:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    self.dfs(grid, i, j, m, n)
        return count
    
    
    def dfs(self, grid, i, j, m, n):
        if i < 0&nbs***bsp;i >= m&nbs***bsp;j < 0&nbs***bsp;j >= n&nbs***bsp;grid[i][j] == '0':
            return
        grid[i][j] = '0'
        self.dfs(grid, i-1, j, m, n)
        self.dfs(grid, i+1, j, m, n)
        self.dfs(grid, i, j-1, m, n)
        self.dfs(grid, i, j+1, m, n)

发表于 2021-09-11 23:36:37 回复(0)

Python 3

抚琴尘世客

class Solution:
# dfs
def solve(self , grid):
# 防止为空
if not grid:
return 0
# dfs
def dfs(grid, row, col, m, n):
if row < 0 or row >= m or col < 0 or col >= n:
return
if dp[row][col] == True or grid[row][col] == '0':
return
# 标记当前岛屿已被遍历
dp[row][col] = True
# 遍历[i][j]岛屿其他陆地
dfs(grid, row - 1, col, m, n)
dfs(grid, row, col - 1, m, n)
dfs(grid, row + 1, col, m, n)
dfs(grid, row, col + 1, m, n)

m, n = len(grid), len(grid[0])
# 遍历过的为True
dp = [[False] * n for _ in range(m)]
# 存储结果
res = 0
for i in range(m):
for j in range(n):
# 当前是岛屿且未被遍历过
if grid[i][j] == '1' and dp[i][j] == False:
dfs(grid, i, j, m, n)
res += 1
return res

发表于 2021-08-25 16:30:13 回复(0)

Python 3

可恶，被他装到了

#
# 判断岛屿数量
# @param grid char字符型二维数组
# @return int整型
#
class Solution:
def solve(self , grid ):
islandnum = 0
for rownum,row in enumerate(grid):
for colnum,col in enumerate(row):
if grid[rownum][colnum] == '1':
islandnum += 1
grid = self.greedsink(grid, rownum, colnum)
return islandnum

def greedsink(self, grid, x, y):
if x < 0 or y < 0 or x > len(grid)-1 or y > len(grid[0])-1 :
return grid
elif grid[x][y] == '1':
grid[x][y] = '0'
grid = self.greedsink(grid, x+1, y)
grid = self.greedsink(grid, x-1, y)
grid = self.greedsink(grid, x, y+1)
grid = self.greedsink(grid, x, y-1)
return grid

# write code here

发表于 2021-08-22 18:15:04 回复(0)

Python 3

Stephenling

#
# 判断岛屿数量
# @param grid char字符型二维数组
# @return int整型
#
class Solution:
def solve(self , grid ):
# write code here
if not grid:
return 0

def dfs(i, j):
grid[i][j] = '0'
for x, y in [(i-1,j), (i+1,j), (i, j-1), (i, j+1)]:
if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
dfs(x, y)

m, n = len(grid), len(grid[0])
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
res += 1
dfs(i, j)
return res

发表于 2021-08-10 22:06:10 回复(0)

Python 3

面朝大海z

#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
# 16:46-17:00
class Solution:
    def solve(self , grid ):
        # write code here
        def dfs(i,j):
            if i >= m&nbs***bsp;j >= n&nbs***bsp;i < 0&nbs***bsp;j < 0:
                return
#             print(i,j,grid[i][j]=="1", visit[i][j])
            if grid[i][j] == "1" and visit[i][j] == False:
                visit[i][j]=True
                dfs(i-1,j)
                dfs(i+1,j)
                dfs(i,j-1)
                dfs(i,j+1)
            pass
        # 行
        m = len(grid) 
        # 列
        n = len(grid[0])
        # visit数组
        visit = [[False]*n for _ in range(m)]
        ans = []
        for i in range(m):
            for j in range(n):
                if visit[i][j] == False and grid[i][j] == "1":
                    ans.append(1)
                dfs(i,j)
                
        return sum(ans)

发表于 2021-08-08 17:14:28 回复(0)

Python 3