网站怎样建设才叫人性化,驻马店网络,网络服务器故障怎么解决,网站域名注册哪个好题目
有一个二维数组#xff0c;其中每个元素要么是1或者0#xff0c;1表示土地#xff0c;连起来的1表示一个岛屿#xff0c;0表示海#xff0c;请计算出来二维数组用有多少个岛屿
比如#xff1a;
{{1, 1, 1, 0, 1},{0, 1, 0, 1, 0},{1, 0, 1, 1, 1},{1, 1, 0, 1, 0…题目
有一个二维数组其中每个元素要么是1或者01表示土地连起来的1表示一个岛屿0表示海请计算出来二维数组用有多少个岛屿
比如
{{1, 1, 1, 0, 1},{0, 1, 0, 1, 0},{1, 0, 1, 1, 1},{1, 1, 0, 1, 0}};
可以看出这二维数组中有四个岛屿
解题
通过深度优先来做遍历过的需要做标记碰到1开始递归标记相邻的1碰到0就return
public class NumIslandsTest {public static void main(String[] args) {int[][] dots {{1, 0, 1, 0, 1}, {0, 1, 0, 1, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 0}};int num getNumIslands(dots);System.out.println(num);}private static int getNumIslands(int[][] dots) {int result 0;for (int i 0; i dots.length; i) {for (int j 0; j dots[i].length; j) {if (dots[i][j] 1) {result;mark(dots, i, j);}}}return result;}private static void mark(int[][] dots, int i, int j) {int iMax dots.length;int jMax dots[0].length;if (i iMax || j jMax || i 0 || j 0) {return;}if (dots[i][j] ! 1) {return;}dots[i][j] 2;mark(dots, i - 1, j);mark(dots, i, j 1);mark(dots, i 1, j);mark(dots, i, j - 1);}
}
