Java学习手册：（数据结构与算法-数组）Number of Islands（leetcode200）
题目：
给的一个二维数组，只含有0和1两个字符。其中1代表陆地，0代表水域。横向和纵向的陆地连接成岛屿，被水域分隔开。问给出的地图中有多少岛屿？
示例一：
输入：
11110
11010
11000
00000
输出：
1
示例二：
输入：
11000
11000
00100
00011
输出：
2
思路：
flood fill方法
代码如下：
package com.haobi; public class NumberofIslands { private static int m, n; // 搜索顺序 private static int d[][] = {{-1,0},{0,1},{1,0},{0,-1}}; private static boolean visited[][]; private static boolean inArea(int x, int y) { return x>=0 && x<m && y>=0 && y<n; } public static void main(String[] args) { //示例1 char[][] c1 = {{'1','1','1','1','0'}, {'1','1','0','1','0'}, {'1','1','0','0','0'}, {'0','0','0','0','0'}}; //示例2 char[][] c2 = {{'1','1','0','0','0'}, {'1','1','0','0','0'}, {'0','0','1','0','0'}, {'0','0','0','1','1'}}; System.out.println(numIslands(c2)); } public static int numIslands(char[][] grid) { m = grid.length; n= grid[0].length; //初始化 visited = new boolean[m][n]; int res = 0; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(grid[i][j] == '1' && !visited[i][j]) { res++; dfs(grid, i, j); } } } return res; } /** * 递归算法 * 从grid[x][y]的位置开始，进行floodfill * 保证（x,y）是合法的，且grid[x][y]是没有被访问过的陆地 * @param grid * @param x * @param y */ private static void dfs(char[][]grid, int x, int y) { visited[x][y] = true; //搜索四个方向 for(int i=0;i<4;i++) { int newx = x + d[i][0]; int newy = y + d[i][1]; if(inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1') { dfs(grid, newx, newy); } } return; } }程序输出结果如下：
3