栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

LintCode 199·判断连接 宽度优先搜索详解 C++/C

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LintCode 199·判断连接 宽度优先搜索详解 C++/C

给定整数矩阵arr以及整数k,确定是否arr中值为k的所有单元是否都连接在一起。 如果矩阵中的两个单元在水平或垂直方向上相邻且具有相同的值,则视为连接。

输入:arr=[
[2,2,2,0],
[0,0,0,2],
[0,1,0,2],
[1,1,1,2]]
k=2
输出:false
解释:不是所有的2都相互连接

算法分析:这个题目我一开始的思路很直接,找到第一个k值,把他改为k+1,然后遍历他与他相连的所有k值,将其改为k+1。再遍历一遍数组,如果数组中还有k值的话,那就证明原数组中的k不是连通的,反之就是连通的。
当然还有另一种思路,使用bfs找出一块k值之后记录数量为1,继续查找数组剩下的元素,如果又查到一块的话则返回false。

这两种思路超过的提交数都蛮低的,但这是我能想到的最优的方法了,如果有更快的方法,希望可以指点一下。

class Solution {
public:
    

	//上下左右
    int v[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
    void BPS(vector> &arr,int i,int j,int k,int m,int n)
    {
        if(i>=0&&i=0&&j> &arr, int k) {
        // Write your code here.

        int m=arr.size();
        int n=arr[0].size();

        int firsti,firstj;
        for(int i=0;i 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/769052.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号