数据结构与算法:算法 -岛屿问题及其现实应用(扫雷)

前几天群里小伙伴们在讨论leetcode的岛屿问题算法,我一看给看乐了,这不就是扫雷扫空地的算法吗,当初自己开始学习编程的时候,是从html和js开始学的,为了让自己学的投入一点就从零开发了个网页版的扫雷,纯html+js+css完成埋雷标记扫空地等操作。因为是用tr和td构建的版面,所以大于9*9必然卡爆,在这就不细谈了,总之当时就有了能够解决岛屿问题的思路。

岛屿问题

问题

思路及解法

具体思路就是遍历二维数组,遇到数值为1的(即岛屿)就将它自己和其上下左右的数值修改为-1(标记),并使用递归重复上述过程,这样就会将初始数值上下左右所有相连的的岛屿标记为已查询过并给计数器加1,遇到数值为0(即水)或者-1(已标记)直接跳过,等到整个二维数组全部遍历一遍之后就得到了岛屿数量。

package xyz.liuzhuoming;

public class Main {

public static void main(String[] args) {
for (int i = 0; i < islands.length; i++) {
for (int j = 0; j < islands[0].length; j++) {
index = findAdjacentElement(i, j) ? index + 1 : index;
}
}
System.out.println(index);
}

/**
* 岛屿数量
*/
private static int index = 0;

/**
* 岛屿二维数组
*/
private static final int[][] islands = {
{1, 1, 1, 1, 0},
{1, 1, 0, 1, 0},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 0},
};

/**
* 标记并查找相邻元素
*
* @param v 列
* @param h 行
*/
private static boolean findAdjacentElement(int v, int h) {
if (v >= 0 && h >= 0 && v < islands.length && h < islands[0].length) {
if (islands[v][h] == 1) {
islands[v][h] = -1;
findAdjacentElement(v - 1, h);
findAdjacentElement(v + 1, h);
findAdjacentElement(v, h - 1);
findAdjacentElement(v, h + 1);
return true;
}
}
return false;
}
}

如果做成一个gif图片大概就是扫雷游戏在区大雷少的情况下开场点一下左上角,一片空地被相继扫出来的样子吧。

所以下次要是再有人说算法无用时,可以甩出这个案例给他看,虽然工作用不到,但是自己做小游戏还是有的用的啊(并没有)
下次可能会分享一下以前写的迷宫小游戏的迷宫生成算法。