大佬教程收集整理的这篇文章主要介绍了1020. 飞地的数量,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1:
输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]输出:3解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。示例 2:
输入:grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]输出:0解释:所有 1 都在边界上或可以到达边界。
提示:
@H_335_0@m == grid.lengthn == grid[i].length1 <= m, n <= 500grid[i][j] 的值为 0 或 1广度优先搜索
class Solution: def numEnclaves(self, grid: List[List[int]]) -> int: if not grid: return 0 l1, l2 = len(grid), len(grid[0]) queue, records = list(), list() for i in range(l1): if grid[i][0] == 1: queue.append([i, 0]) if grid[i][l2 - 1]: queue.append([i, l2-1]) for j in range(l2): if grid[0][j] == 1: queue.append([0, j]) if grid[l1 - 1][j] == 1: queue.append([l1 - 1, j]) directions = [[0, 1], [0, -1], [1, 0], [-1, 0]] while queue: num = queue.pop(0) x, y = num[0], num[1] if num not in records: records.append(num) else: conTinue for direction in directions: _x, _y = x + direction[0], y + direction[1] if 0 <= _x < l1 and 0 <= _y < l2: if (grid[_x][_y] == 1): if ([_x, _y] not in records): queue.append([_x, _y]) count = 0 # 取到所有为1的数量 for i in range(l1): for j in range(l2): if (grid[i][j] == 1 and [i, j] not in records): count += 1 return count
深度优先搜索
class Solution: def numEnclaves(self, grid: List[List[int]]) -> int: if not grid: return 0 l1, l2 = len(grid), len(grid[0]) visit = [[false] * l2 for _ in range(l1)] def dfs(x, y): if x < 0 or x >= l1 or y < 0 or y >= l2 or not grid[x][y] or visit[x][y]: return visit[x][y] = True directions = [[0,1],[0,-1], [1,0],[-1, 0]] for direction in directions: _x, _y = x + direction[0], y + direction[1] if 0 <= _x < l1 and 0 <= _y < l2: if grid[_x][_y]: dfs(_x, _y) for i in range(l1): if grid[i][0]: dfs(i, 0) if grid[i][l2 - 1]: dfs(i, l2 - 1) for j in range(l2): if grid[0][j]: dfs(0, j) if grid[l1 - 1][j]: dfs(l1 - 1, j) count = 0 for i in range(l1): for j in range(l2): if grid[i][j] and not visit[i][j]: count += 1 return count
以上是大佬教程为你收集整理的1020. 飞地的数量全部内容,希望文章能够帮你解决1020. 飞地的数量所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。