1410. Matrix Water Injection

Basically, use BFS to solve it.

1. Start from (R,C), explore all four neighbor points,

2. add the unvisited ones into applicants,

3. test height of points in applicants, add the ones which lower than current point into frontiers,

4. test points in frontiers, if any one is in borders, return "YES",

5. otherwise, go on exploring the points in frontiers.

class Solution:
    """
    @param matrix: the height matrix
    @param R: the row of (R,C)
    @param C: the columns of (R,C)
    @return: Whether the water can flow outside
    """
    def __init__(self):
        self.record = list() # record the visited points
        
    def waterInjection(self, matrix, R, C):
        start = (R,C)
        if any((R==0, R==len(matrix)-1, C==0, C==len(matrix[0])-1)):
            return "YES"
        self.record.append(start)
        return self.explore(start, matrix)
        
    def explore(self, cur, matrix):
        # current point
        (i, j) = cur 
        # all unvisited neighbors
        applicants = [x for x in [(i+1,j), (i,j+1), (i-1,j), (i,j-1)] if x not in self.record]
        
        frontier = list()
        for p in applicants:
            if matrix[p[0]][p[1]] < matrix[i][j]:
                frontier.append(p)
                
        # test frontiers        
        for p in frontier:
            self.record.append(p)
            # when the water in any border of matrix, it can flow out
            if any((p[0]==0, p[0]==len(matrix)-1, p[1]==0, p[1]==len(matrix[0])-1)):
                return "YES"
                
        # go on exploring        
        for p in frontier:
            result = self.explore(p, matrix)
            if result == "YES":
                return "YES"
        return "NO"