首页 > 编程语言 >11.14算法

11.14算法

时间:2023-11-14 11:35:23浏览次数:37  
标签:int res 11.14 dfs ++ 算法 grid size

题目

岛屿数量
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

示例 1:

输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1
示例 2:

输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3

提示:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

答案

class Solution {
public:
void dfs(int i, int j, vector<vector> &grid)
{
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == '0')
{
return;
}
grid[i][j] = '0';
dfs(i - 1, j, grid);
dfs(i, j - 1, grid);
dfs(i, j + 1, grid);
dfs(i + 1, j, grid);
}
int numIslands(vector<vector> &grid)
{
int res = 0;
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] == '1')
{
res++;
dfs(i , j, grid);
}
}
}
return res;
}
};

关键

dfs,找到1个1,剩下的都让它为0就行

标签:int,res,11.14,dfs,++,算法,grid,size
From: https://www.cnblogs.com/minipython-wldx/p/17831212.html

相关文章

  • DES对称加密算法Java实现
    DES对称加密算法Java实现源代码AESUtils.java//packageme.muphy.util;importjavax.crypto.*;importjavax.crypto.spec.SecretKeySpec;importjava.nio.charset.StandardCharsets;importjava.security.InvalidKeyException;importjava.security.NoSuchAlgorithmExcept......
  • 最小生成树求解算法-普利姆算法
    使用场景对于连通图从一点出发到达其他各点有很多条路径,但是我们要求最小生成树包含的点和边,最小生成树边=点-1;用途在于:求解一地到其他地点最短布线问题。要求:最小生成树(1)包含所有点(2)点点间只有一条通路相对于克鲁什卡尔算法,适用于稠密图,与边数无关。编码-输入图,minD......
  • nfls 11.14
    这回感觉每个题都可做,但是每个题目貌似又是都不可以做,思路到中间然后就断了,下午补题然后再看吧。T1这个题目可以推出来的性质有:我们填入的\(b\)数组一定是若干个质数的一次方的乘积组成。当我们确定了\(b_n\)时,我们这个\(b\)序列也就唯一固定。但是最后一位怎么决策......
  • 图的最小生成树算法设计
    二叉树设计实验名称:二叉树设计(1)实验目的:1)掌握二叉树的逻辑结构。2)掌握二叉树的二叉链表存储结构;3)掌握基于二叉链表存储的二叉树的遍历等操作的实现。(2)主要内容:1)定义二叉链存储结构。2)实现二叉树的建立(利用扩展先序序列建立二叉链表存储的二叉树)、二叉树的遍历、统计二叉树结点......
  • 11.14每日总结
    今天早上课上进行了大型数据库的实验二1.实验目的(1)理解HDFS在Hadoop体系结构中的角色;(2)熟练使用HDFS操作常用的Shell命令;(3)熟悉HDFS操作常用的JavaAPI。2.实验平台(1)操作系统:Linux(建议Ubuntu16.04或Ubuntu18.04);(2)Hadoop版本:3.1.3;(3)JDK版本:1.8;(4)JavaIDE:Eclipse。3.实验步骤......
  • 刷题笔记——基础算法(C)
    2181.合并零之间的节点-力扣(LeetCode)给你一个链表的头节点 head ,该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val==0 。对于每两个相邻的 0 ,请你将它们之间的所有节点合并成一个节点,其值是所有已合并节点的值之和。然后将所有 0......
  • 算法学习笔记(38): 2-SAT
    SAT问题,也就是可满足性问题BooleanSatisfiabilityProblem,是第一个被证明的NPC问题。但是特殊的2-SAT我们可以通过图论的知识在线性复杂度内求解,构造出一组解。基本的模型在P4782【模板】2-SAT中有体现。经典的标志是:AB至少选一个,AB要么都选,要么都不选。简单的我......
  • 算法刷题记录-链表移除元素
    算法刷题记录-链表移除元素移除链表元素给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输出:[]示例3:输入:hea......
  • 11.14
    本次我们连着上次的代码继续实现,剩下最后一个教学副院长类后端PresidentControllerpackagecom.example.controller;importcom.example.pojo.Result;importcom.example.service.PresidentService;importorg.springframework.beans.factory.annotation.Autowired;impor......
  • 11.13算法
    题目二叉搜索树中第K小的元素给定一个二叉搜索树的根节点root,和一个整数k,请你设计一个算法查找其中第 k 个最小元素(从1开始计数)。示例1:输入:root=[3,1,4,null,2],k=1输出:1示例2:输入:root=[5,3,6,2,4,null,null,1],k=3输出:3提示:树中的节点数为n。......