What is wrong in this DFS solution?


  • 0
    D
    • 45/48 tests passed.
    • I don't know what am I missing here.
    
    var updateMatrix = function(matrix) {
        
          
      let copyMatrix = Array.from(Array(matrix.length), () => -1);
      copyMatrix = copyMatrix.map(function(e) { return Array.from(Array(matrix[0].length), () => -1); });
      
    
      let isVisitedMat = Array.from(Array(matrix.length), () => 0);
      isVisitedMat = isVisitedMat.map(function(e) { return Array.from(Array(matrix[0].length), () => 0); });
      
      
      for(let i = 0; i < matrix.length; i++){
        for(let j = 0; j < matrix[0].length; j++){
            dfsUtil([i,j], 0);
        }
      }
    
      for(let i = 0; i < copyMatrix.length; i++){
        for(let j = 0; j < copyMatrix[0].length; j++){
            if(copyMatrix[i][j] !== 0){
                getMinDistance([i,j]);
            }
            
        }
      }
      
      
      console.log(copyMatrix);
      
      return copyMatrix;
    
      function dfsUtil(point, dist){
    
       //  if(isVisited(point) || !isSafe(point)){
      	// 	//return Number.MAX_VALUE;
      	//     return;
      	// }
    	
    	isVisitedMat[point[0]][point[1]] = 1;
      	if(matrix[point[0]][point[1]] === 0){
      		copyMatrix[point[0]][point[1]] = 0;
      		return 1;
      	} 
    
      	if(dist > 1000){
      	    return dist;
      	}
    
      	let adjPts = getAdjPoints(point);
      	let distances = [];
      	adjPts.forEach(function(currentPoint){
      		if(!isVisited(currentPoint) && isSafe(currentPoint)){
      			distances.push(dfsUtil(currentPoint, dist + 1));
      		} else if(isVisited(currentPoint) && copyMatrix[currentPoint[0]][currentPoint[1]] > -1){
    			distances.push(copyMatrix[currentPoint[0]][currentPoint[1]] + 1);	
      		}
      	});
    
      	copyMatrix[point[0]][point[1]] = Math.min(...distances);
      	return copyMatrix[point[0]][point[1]] + 1;
    
    
      	// copyMatrix[point[0]][point[1]] = 
      	// 	Math.min(dfsUtil([point[0] + 1, point[1]], dist), dfsUtil([point[0], point[1] + 1], dist));
      	// return dist;
      }
    
      function isVisited(point){
      	return isVisitedMat[point[0]] && isVisitedMat[point[0]][point[1]];
      }
    
      function isSafe(point){
        let i = point[0];
        let j = point[1];
    
        return (i > -1 && i < matrix.length) && (j > -1 && j < matrix.length);
      }
    
      function getAdjPoints(point){
        
        let adjPoints = [];
        
        let i = point[0];
        let j = point[1];
        
        if(i - 1 > -1){
          adjPoints.push([i - 1, j]);
        }
        
        if(i + 1 < matrix.length){
          adjPoints.push([i + 1, j]);
        }
        
        if(j - 1 > -1){
          adjPoints.push([i, j - 1]);
        }
        
        if(j + 1 < matrix[0].length){
          adjPoints.push([i, j + 1]);
        }
        
        return adjPoints;
      }
      
    
      function getMinDistance(point){
      	let adjPts = getAdjPoints(point);
      	let distances = [];
      	adjPts.forEach(function(currentPoint){
      	    
      		distances.push(copyMatrix[currentPoint[0]][currentPoint[1]] + 1);
      	});
    
      	copyMatrix[point[0]][point[1]] = Math.min(...distances);
      }
      
     
        
    };
    
    
    
    

Log in to reply
 

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