本文介绍: 海洋岛屿地图可以用由0、1组成的二维数组表示,水平或竖直方向相连的一组1表示一个岛屿,请计算最大的岛屿的面积(即岛屿中1的数目)。例如,在下图中有4个岛屿,其中最大的岛屿的面积为5。
题目
海洋岛屿地图可以用由0、1组成的二维数组表示,水平或竖直方向相连的一组1表示一个岛屿,请计算最大的岛屿的面积(即岛屿中1的数目)。例如,在下图中有4个岛屿,其中最大的岛屿的面积为5。
分析
将岛屿转换成图之后,岛屿的面积就变成子图中节点的数目。如果能计算出每个连通子图中节点的数目,就能知道最大的岛屿的面积。
可以逐一扫描矩阵中的每个格子,如果遇到一个值为1的格子并且它不在之前已知的岛屿上,那么就到达了一个新的岛屿,于是搜索这个岛屿并计算它的面积。在比较所有岛屿的面积之后就可以知道最大的岛屿的面积。
二维数组dirs表示在矩阵中向上、下、左、右这4个方向前进一步时坐标的变化。在矩阵中向上移动一步时行号减1而列号不变,所以坐标的改变值为(-1,0),其他方向的改变值类似。用当前坐标pos加上坐标的改变值就得到向不同方向前进一步之后的坐标。这样写代码的好处是容易用一个简洁的循环实现向4个不同方向前进。
解:广度优先搜索
解:基于栈实现深度优先搜索
解:基于递归实现深度优先搜索
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。