博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode 695 Max Area of Island
阅读量:5882 次
发布时间:2019-06-19

本文共 1446 字,大约阅读时间需要 4 分钟。

题目详情

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.)

输入一个非空的二维数组,数组由0和1组成。其中0代表水域,1表示陆地。我们需要找出整个数组所表示的地图中,面积最大的一块陆地(陆地的相连只看上下左右相邻的4个元素,如左上方这种就不算相邻!)。

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]]
返回6. 注意答案并不是11, 因为陆地相连要求必须是在上下左右四个方向。
Example 2:
[[0,0,0,0,0,0,0,0]]
返回应为0.

想法

  • 我们还是要遍历数组中的每一个元素。
  • 如果数组元素值为1,则我们以这个值为起点进行深度优先搜索。
  • 遍历当前元素的相邻元素,如果有相邻元素的值为1,那么再以这个元素为起点继续搜索。
  • 为了防止重复,我们每发现一个值为1的元素,就将这个元素赋值为0,代表我们已经遍历过这个元素了。

解法

int[][] directions = {
{-1,0},{1,0},{0,-1},{0,1}}; public int maxAreaOfIsland(int[][] grid) { int rows = grid.length; int cols = grid[0].length; int maxArea = 0; int currArea = 0; for(int row=0;row
=0 && newX < grid.length && newY >=0 && newY < grid[0].length){ if(grid[newX][newY] == 1){ grid[newX][newY] = 0; area += findArea(grid,newX,newY); } } } return area; }

转载地址:http://tkvix.baihongyu.com/

你可能感兴趣的文章
Vue后台管理系统用户认证封装
查看>>
swift - tableview 滚动到指定位置
查看>>
死亡的颂唱者 NOIP模拟 贪心 DFS
查看>>
PHPer面试指南-MySQL 篇
查看>>
1022: [SHOI2008]小约翰的游戏John
查看>>
上传服务端
查看>>
用两个队列实现栈
查看>>
Windows上搭建Standalone模式的Spark环境
查看>>
sql server2005恢复数据库
查看>>
zabbix企业级监控之监控MYSQL主从
查看>>
【redis源码】(八) Intset.c
查看>>
非设计师的基本设计原则【翻译器搬运】
查看>>
V4L2视频输入框架-V4L2 device
查看>>
Mybatis必会的动态SQL
查看>>
网络编程-第三节
查看>>
Linux C++ 控制结构
查看>>
报表网红是Tableau,提测网红是MadPecker
查看>>
栈的链式存储实现
查看>>
Python爬虫【四】Scrapy+Cookies池抓取新浪微博
查看>>
Linux 时间矫正命令
查看>>