leetcode-695-Max Area of Island(BFS)

题目描述:

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[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]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50.

要完成的函数:

int maxAreaOfIsland(vector<vector<int>>& grid) 

说明:

1、给定一个二维矩阵,其中只含有0和1,0表示水域,1表示陆地,要求返回这片地方中最大的一块陆地的面积。

2、这其实是一道深度优先搜索或者广度优先搜索的题目。

由于DFS要用到递归,比较麻烦,所以笔者选择了BFS来实现,定义了一个队列。

代码如下:(附详解)

    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        queue<int>q1;
        int hang=grid.size(),lie=grid[0].size(),sum=0,sum1=0,i=0,j=0,t1=0,t2=0;
        while(i<hang)//每一行的处理
        {
            while(j<lie)//每一列的处理
            {
                if(grid[i][j]==1)//如果搜索到一个1了
                {
                    q1.push(i);//把行坐标塞到队列里面去
                    q1.push(j);//把列坐标塞到队列里面去
                    grid[i][j]=0;//并将这个点改为陆地,避免后面再次搜索到,重复计算
                    sum1=0;//统计当前陆地的面积
                    while(!q1.empty())//当队列非空时,迭代处理
                    {
                        t1=q1.front();//取出行坐标
                        q1.pop();
                        t2=q1.front();//取出列坐标
                        q1.pop();
                        sum1++;
                        if(t1-1>=0&&grid[t1-1][t2]==1)//判断上方有没有陆地
                        {
                            q1.push(t1-1);
                            q1.push(t2);
                            grid[t1-1][t2]=0;//置为0,避免再次搜索到,重复计算
                        }
                        if(t1+1<hang&&grid[t1+1][t2]==1)//判断下方有没有陆地
                        {
                            q1.push(t1+1);
                            q1.push(t2);
                            grid[t1+1][t2]=0;
                        }
                        if(t2-1>=0&&grid[t1][t2-1]==1)//判断左方有没有陆地
                        {
                            q1.push(t1);
                            q1.push(t2-1);
                            grid[t1][t2-1]=0;
                        }
                        if(t2+1<lie&&grid[t1][t2+1]==1)//判断右方有没有陆地
                        {
                            q1.push(t1);
                            q1.push(t2+1);
                            grid[t1][t2+1]=0;
                        }
                    }    
                    sum=max(sum,sum1);//取每次陆地面积的最大值
                }
                j++;
            }
            i++;
            j=0;//j=0记得要加上
        }
        return sum;
    }

上述代码实测30ms,beats 80.17% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏QQ音乐技术团队的专栏

Android Native 开发之 NewString 与 NewStringUtf 解析

本文将从一个 Native Crash 分析入手,带大家了解我们平时开发中,那些容易忽略但又很值得学习的底层源码知识。

1.6K90
来自专栏计算机视觉与深度学习基础

Leetcode 164 Maximum Gap 桶排序好题

Given an unsorted array, find the maximum difference between the successive ele...

22350
来自专栏函数式编程语言及工具

Scala Macros - 元编程 Metaprogramming with Def Macros

    Scala Macros对scala函数库编程人员来说是一项不可或缺的编程工具,可以通过它来解决一些用普通编程或者类层次编程(type level pr...

32090
来自专栏calmound

Contest - 中南大学第六届大学生程序设计竞赛(Semilive)

题1:1160十进制-十六进制 注意他给的数据范围 2^31,int是 2^31-1 #include<iostream> using namespace st...

27540
来自专栏owent

POJ PKU 2549 Sumsets 解题报告

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

9810
来自专栏专知

Numpy教程第2部分 - 数据分析的重要功能

【导读】Numpy是python数据分析和科学计算的核心软件包。 上次介绍了numpy的一些基础操作。例如如何创建一个array,如何提取array元素,重塑(...

47290
来自专栏SeanCheney的专栏

《Pandas Cookbook》第06章 索引对齐1. 检查索引2. 求笛卡尔积3. 索引爆炸4. 用不等索引填充数值5. 从不同的DataFrame追加列6. 高亮每列的最大值7. 用链式方法重现

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

11810
来自专栏数据结构与算法

P1044 栈

题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一...

31760
来自专栏数据结构与算法

UOJ#34. 多项式乘法(NTT)

14200
来自专栏java技术学习之道

Collections.synchronizedMap()、ConcurrentHashMap、Hashtable之间的区别

20340

扫码关注云+社区

领取腾讯云代金券