# 1410. Matrix Water Injection

Basically, use BFS to solve it.

1. Start from (R,C), explore all four neighbor points,&#x20;
2. add the unvisited ones into applicants,&#x20;
3. test height of points in applicants, add the ones which lower than current point into frontiers,&#x20;
4. test points in frontiers, if any one is in borders,  return "YES",&#x20;
5. otherwise, go on exploring the points in frontiers.

```python
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"
        
```
