Solution using DFS


  • 0
    A

    Use DFS from end rows and end columns and maintain 2 visited matrices (one for each river). Solution attached:
    '''
    class Solution(object):
    def dfspt(self,matrix,visited,i,j,m,n):
    visited[i][j]=1;
    if i>0 and matrix[i-1][j]>=matrix[i][j] and visited[i-1][j]!=1:
    visited=self.dfspt(matrix,visited,i-1,j,m,n);
    if j>0 and matrix[i][j-1]>=matrix[i][j] and visited[i][j-1]!=1:
    visited=self.dfspt(matrix,visited,i,j-1,m,n);
    if i<m-1 and matrix[i+1][j]>=matrix[i][j] and visited[i+1][j]!=1:
    visited=self.dfspt(matrix,visited,i+1,j,m,n);
    if j<n-1 and matrix[i][j+1]>=matrix[i][j] and visited[i][j+1]!=1:
    visited=self.dfspt(matrix,visited,i,j+1,m,n);
    return visited;
    def pacificAtlantic(self, matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[List[int]]
    """
    m=len(matrix);
    if m==0:
    return [];
    n=len(matrix[0]);
    visitedp=[[0 for i in range(n)] for j in range(m)];
    visitedq=[[0 for i in range(n)] for j in range(m)];
    for i in range(m):
    visitedp=self.dfspt(matrix,visitedp,i,0,m,n);
    for j in range(n):
    visitedp=self.dfspt(matrix,visitedp,0,j,m,n);
    for i in range(m):
    visitedq=self.dfspt(matrix,visitedq,i,n-1,m,n);
    for j in range(n):
    visitedq=self.dfspt(matrix,visitedq,m-1,j,m,n);
    pts=[];
    for i in range(m):
    for j in range(n):
    if visitedp[i][j]==1 and visitedq[i][j]==1:
    pts.append([i,j]);
    return pts;
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.