当前位置:网站首页>[leetcode] 1254 - count the number of closed Islands
[leetcode] 1254 - count the number of closed Islands
2022-07-02 15:36:00 【Crisp ~】
Two dimensional matrix grid from 0 ( land ) and 1 ( water ) form . The island is made up of the largest 4 Connected in two directions 0 Group composed of , The closed island is a Completely from 1 Surround ( Left 、 On 、 Right 、 Next ) The island of .
Please return Close the island Number of .
Example 1:
Input : grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output : 2
explain :
The islands in the gray area are closed Islands , Because the island is completely surrounded by water ( Namely be 1 The area surrounds ).
Example 2:
Input : grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output : 1
Example 3:
Input : g rid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output : 2
Tips :
- 1 <= grid.length, grid[0].length <= 100
- 0 <= grid[i][j] <=1
# Breadth first traversal
class Solution(object):
def closedIsland(self, grid):
n = len(grid)
m = len(grid[0])
landcount = 0
for i in range(n):
for j in range(m):
if grid[i][j]==0:
val = 1
grid[i][j]=1
queue=[]
queue.append((i,j))
while queue:
x,y = queue[0]
queue.pop(0)
for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
if not 0<=xx<n or not 0<=yy<m:
val=0
elif grid[xx][yy]==0:
grid[xx][yy]=1
queue.append((xx,yy))
landcount+=val
return landcount
# Depth-first traversal
class Solution(object):
def closedIsland(self, grid):
n = len(grid)
m = len(grid[0])
landcount = 0
for i in range(n):
for j in range(m):
if grid[i][j]==0:
val = 1
grid[i][j]=1
stack=[]
stack.append((i,j))
while stack:
x,y = stack[-1]
stack.pop()
for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
if not 0<=xx<n or not 0<=yy<m:
val=0
elif grid[xx][yy]==0:
grid[xx][yy]=1
stack.append((xx,yy))
landcount+=val
return landcount
边栏推荐
- 【LeetCode】417-太平洋大西洋水流问题
- yolo格式数据集处理(xml转txt)
- Kibana basic operation
- 【LeetCode】344-反转字符串
- There are 7 seats with great variety, Wuling Jiachen has outstanding product power, large humanized space, and the key price is really fragrant
- Loss function and positive and negative sample allocation: Yolo series
- 夏季高考文化成绩一分一段表
- 让您的HMI更具优势,FET-G2LD-C核心板是个好选择
- 做好抗“疫”之路的把关人——基于RK3568的红外热成像体温检测系统
- JVM architecture, classloader, parental delegation mechanism
猜你喜欢
随机推荐
Redux - detailed explanation
List set & UML diagram
14_Redis_乐观锁
SQL transaction
飞凌嵌入式RZ/G2L处理器核心板及开发板上手评测
04.进入云原生后的企业级应用构建的一些思考
Pytoch saves tensor to Mat file
你不知道的Set集合
Leetcode skimming -- count the number of numbers with different numbers 357 medium
Force deduction solution summary 2029 stone game IX
The traversal methods of binary tree mainly include: first order traversal, middle order traversal, second order traversal, and hierarchical traversal. First order, middle order, and second order actu
【LeetCode】876-链表的中间结点
15_ Redis_ Redis. Conf detailed explanation
终于搞懂了JS中的事件循环,同步/异步,微任务/宏任务,运行机制(附笔试题)
Libcurl Lesson 13 static library introduces OpenSSL compilation dependency
04_ 栈
【LeetCode】1162-地图分析
Build your own semantic segmentation platform deeplabv3+
13_Redis_事务
folium,确诊和密接轨迹上图