Simple Java DFS solution, no fancy structure


  • 0
    C
     public List<int[]> pacificAtlantic(int[][] matrix) {
    	List<int[]> res = new ArrayList<>();
    	if (matrix.length == 0 || matrix[0].length == 0){
    		return res;
                }
    	int[][] helper = new int[matrix.length][matrix[0].length];
    	for (int i = 0; i < matrix.length; i++) {
    		for (int j = 0; j < matrix[0].length; j++) {
    			FindPath(matrix, helper, i, j);
    		}
    	}
    	for (int i = 0; i < matrix.length; i++) {
    		for (int j = 0; j < matrix[0].length; j++) {
    			if (helper[i][j] == 3) {
    				res.add(new int[] { i, j });
    			}
    		}
    	}
    
    	return res;
    }
    
    private void FindPath(int[][] matrix, int[][] helper, int x, int y) {
    	
    	if (x == matrix.length - 1) {
    		helper[x][y] = helper[x][y] | 2;
    	}
    	if (x == 0) {
    		helper[x][y] = helper[x][y] | 1;
    	}
    	if (y == 0) {
    		helper[x][y] = helper[x][y] | 1;
    	}
    	if (y == matrix[0].length - 1) {
    		helper[x][y] = helper[x][y] | 2;
    	}
    		
    	int[][] direction = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    	for (int[] d : direction) {
    		int x2 = x + d[0];
    		int y2 = y + d[1];
    		if (x2 == matrix.length || x2 < 0 || y2 < 0 || y2 == matrix[0].length) {
    		    continue;
    	    }
    		if (matrix[x][y] <= matrix[x2][y2]&&helper[x][y] != helper[x2][y2]) {
    			helper[x2][y2] = helper[x][y] | helper[x2][y2];
    			FindPath(matrix, helper, x2, y2);
    		}
    	}
    }

Log in to reply
 

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