Javascript A*, TLE 39/53


  • 0
    Y
    const dir = [
      [0, 1],
      [0, -1],
      [1, 0],
      [-1, 0]
    ];
    
    function indexOf(list, target) {
      for (var i = 0; i < list.length; i++) {
        if (list[i].pos[0] === target[0] && list[i].pos[1] === target[1]) {
          return i;
        }
      }
      return -1;
    }
    
    function compare(a, b) {
      if (a.f < b.f)
        return -1;
      if (a.f > b.f)
        return 1;
      return 0;
    }
    
    function reach(forest, start, end) {
      if (start[0] === end[0] && start[1] === end[1])
        return 0;
      var row_size = forest.length;
      var col_size = forest[0].length;
      var open_list = [];
      var close_list = [];
      var g = 0;
      var h = Math.abs(end[0] - start[0]) + Math.abs(end[1] - start[1]);
      var f = g + h;
      open_list.push({
        'pos': start,
        'g': g,
        'f': f,
        'h': h,
        'parent': ''
      });
      while (open_list.length > 0) {
        var top = open_list.shift();
        close_list.push(top);
        for (var i = 0; i < 4; i++) {
          var move = [
            top.pos[0] + dir[i][0],
            top.pos[1] + dir[i][1]
          ];
          if (move[0] < 0 || move[0] >= row_size || move[1] < 0 || move[1] >= col_size || forest[move[0]][move[1]] <= 0) {
            continue;
          }
          var close_idx = indexOf(close_list, move);
          if (close_idx < 0) {
            var open_idx = indexOf(open_list, move);
            if (open_idx < 0) {
              if (move[0] === end[0] && move[1] === end[1]) {
                var step = 0;
                var p = top;
                var output = '';
                while (p != '') {
                  output += p.pos + ' -> ';
                  step++;
                  p = p.parent;
                }
                output += ' ' + step + ' steps';
                return step;
              } else {
                g = top.g + 1;
                h = Math.abs(end[0] - move[0]) + Math.abs(end[1] - move[1]);
                f = g + h;
                var result = {
                  'pos': move,
                  'g': g,
                  'f': f,
                  'h': h,
                  'parent': top
                };
                open_list.push(result);
              }
            } else {
              var old = open_list[open_idx];
              if (old.g > top.g + 1) {
                old.parent = top;
                old.g = top.g + 1;
                old.f = old.g + old.h;
              }
            }
          }
        };
        open_list.sort(compare);
      }
      return -1;
    }
    
    /**
     * @param {number[][]} forest
     * @return {number}
     */
    var cutOffTree = function (forest) {
      if (forest.length === 0 || forest[0].length === 0) {
        return 0;
      }
      var o = [];
      for (var i = 0; i < forest.length; i++) {
        for (var j = 0; j < forest[i].length; j++) {
          var k = forest[i][j];
          if (k > 0)
            o.push([i, j]);
        }
      }
      o.sort(function (a, b) {
          return (forest[a[0]][a[1]] - forest[b[0]][b[1]]);
        });
      var curr = [0, 0];
      var ans = 0;
      for (var i = 0; i < o.length; i++) {
        var step = reach(forest, curr, o[i]);
        if (step === -1)
          return -1;
        ans += step;
        curr = [o[i][0], o[i][1]];
      }
      return ans;
    };
    

Log in to reply
 

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