<commit_before># -*- coding:utf-8 -*-
#
#        Author : TangHanYi
#        E-mail : <EMAIL>
#   Create Date : 2016-12-12 03:59:52 PM
# Last modified : 2016-12-12 04:19:43 PM
#     File Name : Pacific_Atlantic_Water_Flow.py
#          Desc :
import Queue
class Solution(object):

	def findPath(self, i, j, ret, matrix, n, m):
		
		q = Queue.Queue()
		dirX = [-1, 0, 1, 0]
		dirY = [0, -1, 0, 1]
		q.put((i,j))
		while q.empty() == False:
			x, y = q.get()
			for d in range(4):
				x_step = x + dirX[d]
				y_step = y + dirY[d]
				if x_step < 0 or x_step > n or y_step < 0 or y_step > m or matrix[x_step][y_step] == True or matrix[x_step][y_step] > matrix[x][y]:
					continue
				ret[x_step][y_step] = True
				q.put((x_step, y_step))


	def pacificAtlantic(self, matrix):
		
		ret = []

		n = len(matrix)
		if n == 0:
			return ret
		m = len(matrix[0])
		if m == 0:
			return ret
		Pacific = []
		Atlantic = []
		for i in range(n):
			Pacific.append([False for j in range(m)]) 
			Atlantic.append([False for j in range(m)])

		for i in range(n):
			self.findPath(i, 0, Pacific, matrix, n, m)
			self.findPath(i, m - 1, Atlantic, matrix, n, m)

		for i in range(m):
			self.findPath(0, i, Pacific, matrix, n, m)
			self.findPath(n - 1, i, Atlantic, matrix, n, m)

		for i in range(n):
			for j in range(m):
				if Pacific[i][j] == True and Atlantic[i][j] == True:
					ret.append([i,j])

		return ret


if __name__ == "__main__":
	s = Solution()
	matrix = [[]]
	s.pacificAtlantic(matrix)<commit_msg>水流是否能流入不同的海洋<commit_after># -*- coding:utf-8 -*-
#
#        Author : TangHanYi
#        E-mail : <EMAIL>
#   Create Date : 2016-12-12 03:59:52 PM
# Last modified : 2016-12-12 04:39:46 PM
#     File Name : Pacific_Atlantic_Water_Flow.py
#          Desc :
import Queue
class Solution(object):

	def findPath(self, i, j, ret, matrix, n, m):
		
		q = Queue.Queue()
		dirX = [-1, 0, 1, 0]
		dirY = [0, -1, 0, 1]
		q.put((i,j))
		ret[i][j] = True
		while q.empty() == False:
			x, y = q.get()
			for d in range(4):
				x_step = x + dirX[d]
				y_step = y + dirY[d]
				if x_step < 0 or x_step >= n or y_step < 0 or y_step >= m or ret[x_step][y_step] == True or matrix[x_step][y_step] < matrix[x][y]:
					continue
				ret[x_step][y_step] = True
				q.put((x_step, y_step))


	def pacificAtlantic(self, matrix):
		
		ret = []

		n = len(matrix)
		if n == 0:
			return ret
		m = len(matrix[0])
		if m == 0:
			return ret
		Pacific = []
		Atlantic = []
		for i in range(n):
			Pacific.append([False for j in range(m)]) 
			Atlantic.append([False for j in range(m)])

		for i in range(n):
			self.findPath(i, 0, Pacific, matrix, n, m)
			self.findPath(i, m - 1, Atlantic, matrix, n, m)

		for i in range(m):
			self.findPath(0, i, Pacific, matrix, n, m)
			self.findPath(n - 1, i, Atlantic, matrix, n, m)

		for i in range(n):
			for j in range(m):
				if Pacific[i][j] == True and Atlantic[i][j] == True:
					ret.append([i,j])

		return ret


if __name__ == "__main__":
	s = Solution()
	matrix = [[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]]
	print s.pacificAtlantic(matrix)
{'fraction_non_alphanumeric': 0.17542153047989623, 'fraction_numerical': 0.03858625162127108, 'mean_word_length': 2.785276073619632, 'pattern_counts': {'":': 2, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '219049', 'n_tokens_mistral': 1540, 'n_tokens_neox': 1290, 'n_words': 355}