Matrix Water Injection 08/10

Given a two-dimensional matrix, the value of each grid represents the height of the terrain. The flow of water will only flow up, down, right and left, and it must flow from the high ground to the low ground. As the matrix is surrounded by water, it is now filled with water from (R,C) and asked if water can flow out of the matrix.

• The input matrix size is n x n, n <= 200.

• Ensure that each height is a positive integer.

Have you met this question in a real interview? Yes

Example

Given

mat =
[
    [10,18,13],
    [9,8,7],
    [1,2,3]
]

R = 1, C = 1, return "YES"。

Explanation:
(1,1) →(1,2)→Outflow.

Given

mat = 
[
    [10,18,13],
    [9,7,8],
    [1,11,3]
]

R = 1, C = 1, return "NO"。

Explanation:
Since (1,1) cannot flow to any other grid, it cannot flow out.

DFS

public 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
     */
    public String waterInjection(int[][] matrix, int R, int C) {
        // Write your code here
        if(matrix == null || matrix.length == 0){
            return null;
        }
        
        if(dfs(R,C,matrix)){
            return "YES";
        }
        
        return "NO";
    }
    
    
    
    public static int[] xPosition = {1,-1,0,0};
    public static int[] yPosition = {0,0,1,-1};
    
    public boolean dfs(int R, int C, int[][] matrix){
        
        if(!isOUt(R,C,matrix)){
            return true;
        }
        
        for (int i = 0; i < 4 ; i++ ){
            int x = R + xPosition[i];
            int y = R + yPosition[i];
            if(!isOUt(x,y,matrix)){
                return true;
            }
            
            if(matrix[x][y] > matrix[R][C]){
                continue;
            }
            
            if(dfs(x,y,matrix)){
                return true;
            }
        } 
        
        return false;
    }
    
    public boolean isOUt(int i,int j,int[][] matrix){
        if(i<0 || i >= matrix.length || j <0 || j > matrix[0].length){
            return false;
        }
        
        return true;
    }
}

BFS

public 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
     */
     
     
     //bfs
      public String waterInjection(int[][] matrix, int R, int C) {
        // Write your code here
        if(matrix == null || matrix.length == 0){
            return null;
        }
        
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        
        if(bfs(R,C,matrix,visited)){
            return "YES";
        }
        
        return "NO";
        
    }
    
    class Pair{
        public int x;
        public int y;
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        public int getKey(){
            return x;
        }
        
        public int getValue(){
            return y;
        }
    
    }
    
    
    public static int[] xPosition = {1,-1,0,0};
    public static int[] yPosition = {0,0,1,-1};
    
    public boolean bfs(int R, int C, int[][] matrix,boolean[][] visited){
        if(R == 0 || R == matrix.length-1 || C == 0 || C == matrix[0].length-1){
            return true;
        }
        Queue<Pair> queue = new LinkedList<>();
        visited[R][C] = true;
        
        queue.offer(new Pair(R,C));
        
        while(!queue.isEmpty()){
            Pair p = queue.poll();
            int key = p.getKey();
            int value = p.getValue();
            
            for(int i = 0; i < 4; ++i){
                int x = key+xPosition[i];
                int y = value + yPosition[i];
                
                if(matrix[x][y] >= matrix[key][value] || visited[x][y]){
                    continue;
                }
                
                if(x == 0 || x == matrix.length-1 || y == 0 || y == matrix[0].length-1){
                    return true;
                }
                queue.offer(new Pair(x,y));
                visited[x][y] = true;
            }
        }
        
        return false;
        
        
    }