Java教程

每日算法刷题-DFS题目

本文主要是介绍每日算法刷题-DFS题目,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

 

输入:grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
来源:力扣(LeetCode)
链接:岛屿面积题目链接

 解题

采用深度优先遍历DFS:以深度为关键方向,遍历每一个节点,当此节点,连接的节点都访问过,即无房前进时,回退到上一节点,继续访问,遍历全部的节点

所以外层有for()遍历所有节点,然后DFS进行深度遍历

  • 首先分析:从开头进行遍历,对每一个点进行上下左右遍历,如果是1则岛屿数目(这里设一个变量来进行记录)就会加一.
  • 为了防止重复,将访问过的进行赋值0,避免重复访问.
  • 这样我们就可以扩展一个土地块的同时,避免再次访问.

此题代码为

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def DFS(i,j,grid):


            #判断临界条件,达到什么条件时候返回
            if(i==len(grid) or j<0 or j ==len(grid[0]) or i <0):
                return 0
            if(grid[i][j]==1):
                grid[i][j]=0
                return 1+DFS(i-1,j,grid)+DFS(i,j-1,grid)+DFS(i+1,j,grid)+DFS(i,j+1,grid)
            else:
                return 0
        temp=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                temp= max(DFS(i,j,grid),temp)
        return temp 

有点晚了,睡觉

最重要的就是要坚持!!!

觉得还不错的话,点关注可以一起刷题一起进步

这篇关于每日算法刷题-DFS题目的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!