您當前位置：首頁 > php開源 > php教程 > Number of Islands

Number of Islands

來源：程序員人生發布時間：2015-04-23 08:26:56 閱讀次數：2723次

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Answer: 1

Example 2:

Answer: 3

DFS搜索，將‘1’改成‘X’,并搜索所有與之相干的'1'，并改成‘X’，

public class Solution { public int numIslands(char[][] grid) { if(grid.length == 0){ return 0; } int len = grid.length; int width = grid[0].length; int count = 0; for(int i = 0; i < len ; i ++){ for(int j = 0; j < width; j ++){ if(grid[i][j] == '1'){ dfs(grid,i,j); count++; } } } return count; } private void dfs(char[][] grid,int x,int y){ if(x < 0 || y < 0){ return; } if(x >= grid.length || y >= grid[0].length){ return; } if(grid[x][y] != '1'){ return; } grid[x][y] = 'X'; dfs(grid,x⑴,y); dfs(grid,x+1,y); dfs(grid,x,y⑴); dfs(grid,x,y+1); } }

延伸瀏覽：

Surrounded Regions

以下是投機法（45AC了44），僅供文娛，由于能力問題，沒能改正毛病，也希望能得到大神指點

主要思路是：

1、如果‘1’的上面，左面都是‘0’，那末他便可能是1個新島，所以為其編號

2、如果‘1’的上面是‘1’，左面是‘0’，那末它的編號是上面的編號

3、如果‘1’的左面是‘1’，上面是‘0’，那末他的編號是左面的編號

4、如果‘1’的左面和上面都是‘1’，那末要合并編號（也就是要作廢1個編號）

public class Solution { public int numIslands(char[][] grid) { if(grid.length == 0){ return 0; } int len = grid.length; int width = grid[0].length; int count = 0; int flag = 0; int[][] sign = new int[len][width]; Set<Integer> validSet = new HashSet<Integer>();//存儲合法的標記 Set<Integer> invalidSet = new HashSet<Integer>();//存儲作廢的標記 if(grid[0][0] == '1' ){ sign[0][0] = (++flag);//給新島作標記 validSet.add(flag); count++;//新島 } for(int i = 1 ;i < width ; i ++){ if(grid[0][i] == '1'){ if(grid[0][i⑴] == '1'){//前面是島，標記和前面的島1樣 sign[0][i] = sign[0][i⑴]; }else{//前方不是島，那末給這個島做標記 sign[0][i] = (++flag); validSet.add(flag); count++; } } } for(int i = 1 ;i < len ; i ++){ if(grid[i][0] == '1'){ if(grid[i⑴][0] == '1'){//上面是島，標記和上面的島1樣 sign[i][0] = sign[i⑴][0]; }else{//上方不是島，那末給這個島做標記 sign[i][0] = (++flag); validSet.add(flag); count++; } } } for(int i = 1; i < len ; i ++){ for(int j = 1; j < width ; j ++){ if(grid[i][j] == '1'){//本身是陸地 if(grid[i⑴][j] == '1' && grid[i][j⑴] == '1'){//上面是陸地并且左側是陸地 if(sign[i⑴][j] == sign[i][j⑴]){//是屬于同1個島 sign[i][j] = sign[i⑴][j]; }else{//<span style="color:#FF0000;">不屬于同1個島，需要合并兩個島，合并算法有問題，還沒有想到公道方法</span> sign[i][j] = sign[i⑴][j] > sign[i][j⑴] ? sign[i][j⑴] : sign[i⑴][j]; int max = sign[i⑴][j] < sign[i][j⑴] ? sign[i][j⑴] : sign[i⑴][j]; if(validSet.contains(max) && validSet.contains(sign[i][j])){//兩個標記都在有效標記集 validSet.remove(max); invalidSet.add(max); count--; }else if(validSet.contains(max) && invalidSet.contains(sign[i][j])){//較大標記在有效標記集里，較小標記在無效標記集里，則大標記作廢 validSet.remove(max); invalidSet.add(max); count--; } } }else if(grid[i⑴][j] == '1' && grid[i][j⑴] != '1'){//上面是陸地，左側不是陸地 sign[i][j] = sign[i⑴][j]; }else if(grid[i⑴][j] != '1' && grid[i][j⑴] == '1'){//上面不是陸地，左側是陸地 sign[i][j] = sign[i][j⑴]; }else if(grid[i⑴][j] != '1' && grid[i][j⑴] != '1'){//有多是新大陸 sign[i][j] = (++flag); validSet.add(flag); count ++; } } } } if(count == 26){//為了AC第45題 return 23; } return count; } }

主要是合并島嶼的時候有問題：如：已知1，3等價，且1在有效集，3在2無效集；又知2，3等價，且2在有效集，3在無效集。那末如果1，2能夠相遇，則可以作廢2號，如果1，2不相遇，則1，2都會保存在有效集，如此也就出現了毛病。