chipMoving

Bạn được cho một lưới các số nguyên không âm, và một con chíp được đặt ở ô trên cùng bên trái. Mỗi lượt, con chíp có thể di chuyển sang ô bên phải hoặc ô bên dưới. Chi phí di chuyển bằng với số được ghi trên ô kết quả.

Ngoài ra còn có một số chi phí bổ sung nếu bạn thay đổi hướng giữa hai lần di chuyển liên tiếp. Để đổi hướng, bạn sẽ phải trả thêm chi phí là 10.

Số lượng điểm tối thiếu cần để đến góc dưới cùng bên phải của lưới là bao nhiêu?

Giả sử bạn không trả cho việc đứng ở ô phía trên bên trái lúc đầu, vì vậy số ở trên ô đó không tính.

Ví dụ

• Với
  grid = [[ 0,  0, 99, 99, 99],
        [99,  0,  0,  0, 99],
        [99, 99, 99,  0, 99],
        [99, 99, 99,  0, 99],
        [99, 99, 99,  0,  0]]

đầu ra là chipMoving(grid) = 40.
  
  Bạn có thể tránh tất cả ô 99 nhưng bạn cần đổi hướng 4 lần.

Đầu vào/Đầu ra

• [giới hạn thời gian chạy] 0.5 giây 

• [đầu vào] array.array.integer matrix

  Một ma trận các số nguyên không âm.

  Điều kiện tiền đề:
  1 ≤ matrix.length ≤ 100,
  1 ≤ matrix[0].length ≤ 100,
  0 ≤ matrix[i][j] ≤ 2000.

• [đầu ra] integer