Why opt[x][y] = -1 breaks the code (while comment it out pass all the tests)?


  • 0
    C
    public class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix.length == 0)
                return 0;
            int[][] opt = new int[matrix.length][matrix[0].length];
            for(int i=0; i < matrix.length; i++) {
                for(int j=0; j< matrix[0].length; j++) {
                     visit(matrix, opt, i, j);
                }
            }
            int ret = 0;
            for(int i=0; i < matrix.length; i++) {
                for(int j=0; j< matrix[0].length; j++) {
                    ret = Math.max(ret, opt[i][j]);
                }
            }
            return ret;
            
        }
        
        public void visit(int[][] matrix, int[][] opt, int x, int y) {
            if (opt[x][y] != 0)
                return;
            int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
            int m = matrix.length; 
            int n = matrix[0].length;
            //opt[x][y] = -1;
            for(int[] d:dir) {
                int nx = x + d[0];
                int ny = y + d[1];
                if( nx < 0 || nx >= m || ny < 0 || ny >= n || matrix[nx][ny] <= matrix[x][y] || opt[x][y] == -1) {
                    continue;
                }
                visit(matrix, opt, nx, ny);
            }
            opt[x][y] = 1;
            for( int[] d:dir ) {
                int nx = x + d[0];
                int ny = y + d[1];
                if( nx < 0 || nx >= m || ny < 0 || ny >= n || matrix[nx][ny] <= matrix[x][y]) {
                    continue;
                }
                opt[x][y] = Math.max( opt[x][y], opt[nx][ny]+1);
            }
        }
    }

  • 0
    C

    I know it. Because I have a typo when deciding to whether to visit the neighbor.


Log in to reply
 

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