48-51 图论

48. 岛屿数量

给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

class Solution(object): def numIslands(self, grid): m,n=len(grid),len(grid[0]) res=0 def DFS(x,y,m,n,grid): if x>=0 and x<m and y<n and y>=0 and grid[x][y]=="1" : grid[x][y]="0" DFS(x+1,y,m,n,grid) DFS(x-1,y,m,n,grid) DFS(x,y-1,m,n,grid) DFS(x,y+1,m,n,grid) for i in range(m): for j in range(n): if grid[i][j]=="1" : res+=1 DFS(i,j,m,n,grid) return res

49. 腐烂的橘子

在给定的m x n网格grid中，每个单元格可以有以下三个值之一：

• 值0代表空单元格；
• 值1代表新鲜橘子；
• 值2代表腐烂的橘子。

每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。

from collections import deque class Solution(object): def orangesRotting(self, grid): dire=[[1,0],[-1,0],[0,1],[0,-1]] dq=deque() res=-1 count=0 fresh=0 m,n=len(grid),len(grid[0]) for i in range(m): for j in range(n): if grid[i][j]==2: dq.append([i,j]) count=len(dq) if grid[i][j]==1: fresh+=1 if not count and not fresh: return 0 while dq: cur=dq.popleft() for d in dire: x,y=cur[0]+d[0],cur[1]+d[1] if x>=0 and x<m and y>=0 and y<n and grid[x][y]==1: grid[x][y]=2 fresh-=1 dq.append([x,y]) count-=1 if not count: count=len(dq) res+=1 if fresh==0: return res return -1

50. 课程表

你这个学期必须选修numCourses门课程，记为0到numCourses - 1。

在选修某些课程之前需要一些先修课程。 先修课程按数组prerequisites给出，其中prerequisites[i] = [ai, bi]，表示如果要学习课程ai则必须先学习课程bi。

• 例如，先修课程对[0, 1]表示：想要学习课程0，你需要先完成课程1。

请你判断是否可能完成所有课程的学习？如果可以，返回true；否则，返回false。

class Solution(object): def canFinish(self, numCourses, prerequisites): grid=[[0]*numCourses for _ in range(numCourses)] for _ in prerequisites: grid[_[0]][_[1]]=1 self.falg=[0]*numCourses self.res=True def DFS(grid,x,n): if x>=0 and x<n : self.falg[x]=1 for i in range(n): if grid[x][i]==1 : if self.falg[i]==0: DFS(grid,i,n) elif self.falg[i]==1: self.res=False self.falg[x]=2 for i in range(numCourses): for j in range(numCourses): if grid[i][j]==1 and self.falg[i]==0: DFS(grid,i,numCourses) return self.res