给出一个二维数组，数组中全部的数要不是0要不是1，在其中1意味着陆上，也就是岛。0意味着深海。与1邻近的1则觉得归属于同一个岛，求二维数组中岛的总数。
举个例子：
110110000
111011100
010010001
000100011
这样一个二维数组中共有4个岛。
我们可以定义一个感染函数，这个感染函数的输入为二维数组中值为1的一个坐标，通过这个感染函数可以把与这个1连成一片的所有的1都置为2，数字2表示该位置对应的岛已经计算过。
有了这个感染函数，我们可以开始整个算法的流程。初始化岛的数量为0，循环遍历二维数组中的每个元素，如果当前元素是0或2，直接跳过，遍历下一个元素，因为0代表海洋，没有岛，2代表已经计算过的岛，不需要重复计算；如果当前元素为1，则把当前元素的坐标传入到感染函数中，感染函数会把与这个1连成一片的所有的1都置为2，岛的数量加一。
public static int numberOfIsland(int[][] arr) {
int res = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (arr[i][j] == 1) {
infection(arr, i, j); //执行感染函数
res++; } return res; } |
接下来我们来分析如何设计感染函数。我们可以把感染坐标(x, y)的问题化为四个子问题，分别感染(x+1, y)、(x-1, y)、(x, y-1)、(x,y+1)。要感染每个坐标，我们需要首先判断坐标是否越界，然后判断坐标上的值是否为1，任何一个条件不满足，函数都将返回。我们可以使用递归来实现。
感染函数的代码如下：
public static void infection(int[][] arr, int x, int y) {
// 如果坐标越界，或者坐标上的元素不为1，递归函数返回
if (x < 0 || x >= arr.length || y < 0 || y >= arr[0].length || arr[x][y] != 1) { return; } arr[x][y] = 2; // 感染坐标(x, y) infection(arr, x + 1, y); //感染上面 infection(arr, x - 1, y); //感染下面 infection(arr, x, y - 1); //感染左面 infection(arr, x, y + 1); //感染右面 } |
以上就是岛问题。
本文来源于：算法--岛问题-变化吧门户
特别声明：以上文章内容仅代表作者本人观点，不代表变化吧门户观点或立场。如有关于作品内容、版权或其它问题请于作品发表后的30日内与变化吧联系。
- 赞助本站
- 微信扫一扫
-
- 加入Q群
- QQ扫一扫
-
评论