一、二位数组岛屿

1、问题描述

假设一个二维数组，完全有0和1两个数字组成，假设将所有的0认为是海洋，单独的数字1或者连成一片的数字1认为是岛屿，那么求整个二维数组中有多少岛屿，并且打印每个岛屿中的坐标点。

{0,1,0,1,1,0,1,0}, {1,0,0,0,1,0,0,0}, {0,0,1,0,0,1,0,1}, {0,1,0,1,0,0,1,0}, {0,1,1,1,1,0,1,0}, {0,0,1,0,1,0,1,0},

首先，我们可以将数组看做一个围棋棋盘，0或者空位认为是海洋，以下面为例。

2、关于围棋

     围棋，一种策略性两人棋类游戏，中国古时称“弈”，西方名称“Go”。流行于东亚国家（中、日、韩、朝），属琴棋书画四艺之一。围棋起源于中国，传为帝尧所作，春秋战国时期即有记载。隋唐时经朝鲜传入日本，流传到欧美各国。围棋蕴含着中华文化的丰富内涵，它是中国文化与文明的体现。

二、算法实现

1、核心方法

 	/** 	 * 搜素岛屿 	 *  	 * @param islandMap 	 * @return 	 */ 	private static Map<Integer, Point[]> findIsland(int[][] islandMap) {  		Map<Integer, Point[]> zoneMap = new HashMap<Integer, Point[]>(); 		for (int i = 0; i < islandMap.length; i++) { 			int[] row = islandMap[i]; 			for (int j = 0; j < row.length; j++) { 				int pointValue = row[j]; 				if (pointValue == 1) {  					int zoneID = computeIndexAdjustZone(zoneMap, i, j); 					Point[] points = zoneMap.get(zoneID); 					if (points == null) { 						points = new Point[0]; 					} 					Point[] tempPoints = new Point[points.length + 1];  					for (int k = 0; k < points.length; k++) { 						Point point = points[k]; 						tempPoints[k] = point; 					} 					tempPoints[points.length] = new Point(i, j); 					zoneMap.put(zoneID, tempPoints); 				}  			}  		} 		return zoneMap; 	}  	/** 	 * 打印岛屿 	 *  	 * @param zoneMap 	 */ 	private static void printIsland(Map<Integer, Point[]> zoneMap) { 		for (Map.Entry<Integer, Point[]> entry : zoneMap.entrySet()) { 			System.out.println("-----------" + entry.getKey()); 			System.out.println(Arrays.asList(entry.getValue())); 		} 	}  	/** 	 * 计算区域编号并调整map 	 *  	 * @param mapZone 	 * @param i 	 * @param j 	 * @return 	 */ 	private static int computeIndexAdjustZone(Map<Integer, Point[]> mapZone, int i, int j) {  		if (mapZone.size() == 0) { 			return 0; 		} 		// 上下左右变化量，0位x变化量，1位y的变化量 		int[][] coording = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };  		List<Integer> keylist = new ArrayList<Integer>(); 		for (int x = 0; x < coording.length; x++) { 			Point p = new Point(coording[x][0] + i, coording[x][1] + j); 			for (Map.Entry<Integer, Point[]> entry : mapZone.entrySet()) { 				Point[] points = entry.getValue(); 				for (int k = 0; k < points.length; k++) { 					if (p.equals(points[k])) { 						// 搜索到点可能属于多个区域，这个时候我们需要记录下来多个区域的 index 						keylist.add(entry.getKey()); 					} 				} 			} 		}  		if (keylist.size() > 0) { 			// 将多个区域排序 			Collections.sort(keylist); 			// 取出最小的区域 index 			Integer minIndex = keylist.get(0); 			Point[] zonePoints = mapZone.get(minIndex); 			// 如果一个点位属于多个区，那么这个点就是连接点，那么需要将两个区域合并，并且按照最小索引合并 			for (Integer index : keylist) { 				if (index != minIndex) { 					Point[] points = mapZone.remove(index); 					if (points == null) 						continue;  					Point[] tempPoints = new Point[zonePoints.length + points.length]; 					System.arraycopy(zonePoints, 0, tempPoints, 0, zonePoints.length); 					System.arraycopy(points, 0, tempPoints, zonePoints.length, points.length); 					zonePoints = tempPoints; 				} 			} 			mapZone.put(minIndex, zonePoints); 			return minIndex; 		}  		return autoIncrementZoneIndex(mapZone); 	}  	/** 	 * 自动递增zone 	 *  	 * @param mapZone 	 * @return 	 */ 	private static int autoIncrementZoneIndex(Map<Integer, Point[]> mapZone) {  		// 如果没有找到所属区域，那么自动新增一个区域index 		Set<Integer> keys = mapZone.keySet(); 		Iterator<Integer> iterator = keys.iterator(); 		int index = 0; 		while (iterator != null && iterator.hasNext()) { 			Integer next = iterator.next(); 			index = Math.max(index, next); 		} 		if (index == 0 && mapZone.size() == 1) { 			return 1; 		}  		return index + 1; 	}

2、测试

public class SecretIsland {  	public static void main(String[] args) { 		 		int[][] islandMap = { 			{0,1,0,1,1,0,1,0}, 			{1,0,0,0,1,0,0,0}, 			{0,0,1,0,0,1,0,1}, 			{0,1,0,1,0,0,1,0}, 			{0,1,1,1,1,0,1,0}, 			{0,0,1,0,1,0,1,0}, 		}; 		 		Map<Integer, Point[]> zoneMap = findIsland(islandMap); 		printIsland(zoneMap); 	}  }

打印结果如下

-----------0 [java.awt.Point[x=0,y=1]] -----------1 [java.awt.Point[x=0,y=3], java.awt.Point[x=0,y=4], java.awt.Point[x=1,y=4]] -----------2 [java.awt.Point[x=0,y=6]] -----------3 [java.awt.Point[x=1,y=0]] -----------4 [java.awt.Point[x=2,y=2]] -----------5 [java.awt.Point[x=2,y=5]] -----------6 [java.awt.Point[x=2,y=7]] -----------7 [java.awt.Point[x=3,y=1], java.awt.Point[x=4,y=1], java.awt.Point[x=4,y=2],  java.awt.Point[x=3,y=3], java.awt.Point[x=4,y=3], java.awt.Point[x=4,y=4],  java.awt.Point[x=5,y=2], java.awt.Point[x=5,y=4]] -----------9 [java.awt.Point[x=3,y=6], java.awt.Point[x=4,y=6], java.awt.Point[x=5,y=6]]