leetcode200

/* * 广度优先： * queue =[] * queue.append(start) * visited.append(start) * * while queue: * node = queue.pop()遍历当前层的节点 * visited.add() * * process(node) * nodes = gennertae_visited_node(node) * queue.push(nodes)//每次在队列中添加下一层的节点 */

 

采用扩散法和沉岛法

/* * 思路：采用广度优先的扩散搜索 * 1.遍历二维数组，如果遇到1（陆地）则进入递归函数，否则继续遍历 * 2.进入递归函数后，将当前的1（陆地）变为0（海洋） * 3.遍历当前节点的外层节点（四联通扩散），对这些节点进行递归 */ public class Main { static int[] dx = {1,-1,0,0}; static int[] dy = {0,0,1,-1}; public static void main(String[] args) { char[][] grid = {{'1','1','1','1','0'}, {'1','1','0','1','0'}, {'1','1','0','0','0'}, {'0','0','0','0','0'}}; int coun = 0; for(int i = 0;i < grid.length;i++) { for(int j = 0;j < grid[0].length;j++) { if(grid[i][j] == '1') { coun += fin(i,j,grid); } } } System.out.println(coun); } public static int fin(int i ,int j,char[][] g) { if(g[i][j] == '0')//不是陆地，返回0 return 0; g[i][j] = '0';//沉岛 for(int k = 0;k < 4;k++) {//四联通扩散 int nx = i + dx[k],ny = j + dy[k]; if(nx < 0 || nx >= g.length || ny < 0 || ny >= g[0].length) //扩散的节点坐标不满足要求，则跳过该次循环 continue; fin(nx,ny,g);//递归新节点 } return 1; } }