200. Number of Islands(week 3)

200. Number of Islands

题意：

给一个01矩阵，求不同的岛屿的个数。 0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

思路：

dfs和bfs都可以，注意设置好visit，和边界值就可以，非递归利用题目111总结的模板。上代码：

dfs

dfs递归：

import collections; class Solution(object): def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ lengrid = len(grid) if(lengrid == 0): return 0 lenstr = len(grid[0]) visit = [[False for col in range(lenstr)] for row in range(lengrid)] result = 0 for i in range(0, lengrid): for j in range(0, lenstr): if (not visit[i][j] and grid[i][j]=="1"): self.dfs(grid, visit, lengrid, lenstr, i, j) result += 1 return result def dfs(self, grid, visit, lengrid, lenstr, rootX, rootY): visit[rootX][rootY] = True # 上节点 if (rootX - 1 >= 0 and not visit[rootX - 1][rootY] and grid[rootX - 1][rootY] == "1"): self.dfs(grid, visit, lengrid, lenstr, rootX - 1, rootY) # 右节点 if (rootY + 1 < lenstr and not visit[rootX][rootY + 1] and grid[rootX][rootY + 1] == "1"): self.dfs(grid, visit, lengrid, lenstr, rootX, rootY + 1) # 下节点 if (rootX + 1 < lengrid and not visit[rootX + 1][rootY] and grid[rootX + 1][rootY] == "1"): self.dfs(grid, visit, lengrid, lenstr, rootX + 1, rootY) # 左节点 if (rootY - 1 >= 0 and not visit[rootX][rootY - 1] and grid[rootX][rootY - 1] == "1"): self.dfs(grid, visit, lengrid, lenstr, rootX, rootY - 1)

dfs非递归：

class Solution(object): def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ lengrid = len(grid) if(lengrid == 0): return 0 lenstr = len(grid[0]) visit = [[False for col in range(lenstr)] for row in range(lengrid)] result = 0 stack = [] for i in range(0, lengrid): for j in range(0, lenstr): if (not visit[i][j] and grid[i][j]=="1"): self.dfs(grid, visit, lengrid, lenstr, i, j) result += 1 return result def dfs(self, grid, visit, lengrid, lenstr, rootX, rootY): # 栈存储节点坐标，其它位置也可以存储在set里面 stack = [(rootX,rootY)] while(stack): node = stack.pop() visit[node[0]][node[1]] = True rootX = node[0] rootY = node[1] if(node): # 上节点 if (rootX - 1 >= 0 and not visit[rootX - 1][rootY] and grid[rootX - 1][rootY] == "1"): stack.append((rootX - 1, rootY)) # 右节点 if (rootY + 1 < lenstr and not visit[rootX][rootY + 1] and grid[rootX][rootY + 1] == "1"): stack.append((rootX, rootY+1)) # 下节点 if (rootX + 1 < lengrid and not visit[rootX + 1][rootY] and grid[rootX + 1][rootY] == "1"): stack.append((rootX + 1, rootY)) # 左节点 if (rootY - 1 >= 0 and not visit[rootX][rootY - 1] and grid[rootX][rootY - 1] == "1"): stack.append((rootX, rootY-1))

bfs

bfs非递归

bfs非递归模板总结：

放进去队列的都是visit过了的，准备找他是否有还没有visit的邻> 居的，和dfs不一样，dfs是在pop出来的时候才visit，bfs是在进入队列的时候就visit了),参考http://www.cnblogs.com/debuging/archive/2013/07/24/3210027.html）

(1）初始化队列Q；visited[n]=0； （2）访问顶点v；visited[v]=1；顶点v入队列Q； （3） while（队列Q非空） v=队列Q的对头元素出队； w=顶点v的第一个邻接点； while（w存在） 如果w未访问，则访问顶点w； visited[w]=1； 顶点w入队列Q； w=顶点v的下一个邻接点。 class Solution(object): def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ lengrid = len(grid) if(lengrid == 0): return 0 lenstr = len(grid[0]) visit = [[False for col in range(lenstr)] for row in range(lengrid)] result = 0 stack = [] for i in range(0, lengrid): for j in range(0, lenstr): if (not visit[i][j] and grid[i][j]== "1"): queue = [(i,j)] visit[i][j] = True self.bfs(grid, visit, lengrid, lenstr, i, j, queue) result += 1 return result def neighbor(self, grid, visit, lengrid, lenstr, rootX, rootY): # 上节点 if (rootX - 1 >= 0 and not visit[rootX - 1][rootY] and grid[rootX - 1][rootY] == "1"): return (rootX - 1, rootY) # 右节点 if (rootY + 1 < lenstr and not visit[rootX][rootY + 1] and grid[rootX][rootY + 1] == "1"): return (rootX, rootY+1) # 下节点 if (rootX + 1 < lengrid and not visit[rootX + 1][rootY] and grid[rootX + 1][rootY] == "1"): return (rootX + 1, rootY) # 左节点 if (rootY - 1 >= 0 and not visit[rootX][rootY - 1] and grid[rootX][rootY - 1] == "1"): return (rootX, rootY-1) return () def bfs(self, grid, visit, lengrid, lenstr, rootX, rootY, queue): while( queue): # 出队列 node = queue[0] del queue[0] visit[node[0]][node[1]] = True rootX = node[0] rootY = node[1] # 跟节点的临接节点 w = self.neighbor(grid, visit, lengrid, lenstr, rootX, rootY) while(w !=( )) : if( not visit[w[0]][w[1]]): visit[w[0]][w[1]] = True queue.append(w) w = self.neighbor(grid, visit, lengrid, lenstr, rootX, rootY)