#coding=utf-8
# floodfill经典题
# step 1) 从太平洋的边界出发，找到所有能到达太平样的点 TP
# step 2) 从大西洋的边界出发，找到所有能到达大西洋的点 DX
# step 3) 求交集 TP DX
class Solution(object):
def pacificAtlantic(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
self.res = []
if not matrix:
return self.res
self.m = len(matrix)
self.n = len(matrix[0])
self.derecToPacific = [[0,1],[1,0]]
self.derecToAtlantic = [[0,-1],[-1,0]]
self.visitPacific = [[False for i in range(self.n)] for i in range(self.m)]
self.visitAtlantic = [[False for i in range(self.n)] for i in range(self.m)]
self.PacificStart = []
self.AtlanticStart = []
for y in range(self.n):
self.PacificStart.append([0,y])
self.AtlanticStart.append([self.m-1,y])
for x in range(self.m):
self.PacificStart.append([x,0])
self.AtlanticStart.append([x,self.n-1])
# for x in range(self.m):
# self.AtlanticStart.append([x, self.n - 1])
# for y in range(self.n):
# self.AtlanticStart.append([self.m-1, y])
# test
self.toPacific(matrix)
print self.visitPacific
self.toAtlantic(matrix)
print self.visitAtlantic
# self.toPacific(matrix)
# self.toAtlantic(matrix)
#
# for x in range(self.m):
# for y in range(self.n):
# if self.visitAtlantic[x][y] and self.visitPacific[x][y]:
# self.res.append([x,y])
#
# print self.res
# return self.res
def inArea(self,x,y):
return x >= 0 and x < self.m and y >= 0 and y < self.n
def toPacific(self,matrix):
for item in self.PacificStart:
x = item[0]
y = item[1]
if not self.visitPacific[x][y]:
self.dfsToPacific(matrix, x, y)
def dfsToPacific(self,matrix,x,y):
self.visitPacific[x][y] = True
for item in self.derecToPacific:
newX = x + item[0]
newY = y + item[1]
if self.inArea(newX,newY) and not self.visitPacific[newX][newY] and matrix[newX][newY] >= matrix[x][y]:
self.dfsToPacific(matrix,newX,newY)
return
def toAtlantic(self,matrix):
for item in self.AtlanticStart:
x = item[0]
y = item[1]
if not self.visitAtlantic[x][y]:
self.dfsToAtlantic(matrix, x, y)
def dfsToAtlantic(self, matrix, x, y):
self.visitAtlantic[x][y] = True
for item in self.derecToAtlantic:
newX = x + item[0]
newY = y + item[1]
if self.inArea(newX, newY) and not self.visitAtlantic[newX][newY] and matrix[newX][newY] >= matrix[x][y]:
self.dfsToAtlantic(matrix, newX, newY)
return
# 第一版代码错误，应该是4个方向，而不是另个方向
class Solution2(object):
def pacificAtlantic(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
self.res = []
if not matrix:
return self.res
self.m = len(matrix) self.n = len(matrix[0]) self.derection= [[-1,0],[0,1],[1,0],[0,-1]] self.visitPacific = [[False for i in range(self.n)] for i in range(self.m)] self.visitAtlantic = [[False for i in range(self.n)] for i in range(self.m)] self.PacificStart = [] self.AtlanticStart = [] for y in range(self.n): self.PacificStart.append([0,y]) self.AtlanticStart.append([self.m-1,y]) for x in range(self.m): self.PacificStart.append([x,0]) self.AtlanticStart.append([x,self.n-1]) # for x in range(self.m): # self.AtlanticStart.append([x, self.n - 1]) # for y in range(self.n): # self.AtlanticStart.append([self.m-1, y]) # test self.toPacific(matrix) print self.visitPacific self.toAtlantic(matrix) print self.visitAtlantic # self.toPacific(matrix) # self.toAtlantic(matrix) # # for x in range(self.m): # for y in range(self.n): # if self.visitAtlantic[x][y] and self.visitPacific[x][y]: # self.res.append([x,y]) # # print self.res # return self.res def inArea(self,x,y): return x >= 0 and x < self.m and y >= 0 and y < self.n def toPacific(self,matrix): for item in self.PacificStart: x = item[0] y = item[1] if not self.visitPacific[x][y]: self.dfsToPacific(matrix, x, y) def dfsToPacific(self,matrix,x,y): self.visitPacific[x][y] = True for item in self.derection: newX = x + item[0] newY = y + item[1] if self.inArea(newX,newY) and not self.visitPacific[newX][newY] and matrix[newX][newY] >= matrix[x][y]: self.dfsToPacific(matrix,newX,newY) return def toAtlantic(self,matrix): for item in self.AtlanticStart: x = item[0] y = item[1] if not self.visitAtlantic[x][y]: self.dfsToAtlantic(matrix, x, y) def dfsToAtlantic(self, matrix, x, y): self.visitAtlantic[x][y] = True for item in self.derection: newX = x + item[0] newY = y + item[1] if self.inArea(newX, newY) and not self.visitAtlantic[newX][newY] and matrix[newX][newY] >= matrix[x][y]: self.dfsToAtlantic(matrix, newX, newY) returns = Solution2()# mat = [# [1,2,2,3,5],# [3,2,3,4,4],# [2,4,5,3,1],# [6,7,1,4,5],# [5,1,1,2,4]# ]# mat = [# [1,2],# [4,3]## ]mat = [ [1,2,3], [8,9,4], [7,6,5]]s.pacificAtlantic(mat)