Vấn đề: Thời gian để cà chua chín trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào mảng 2D số arr làm đối số duy nhất. Số trong mảng: 0 = ô trống, 1 = cà chua tươi, 2 = cà chua chín. Mỗi phút, cà chua tươi liền kề (4 hướng) với cà chua chín sẽ chín. Hàm trả về số phút tối thiểu cho đến khi không còn cà chua tươi. Nếu không thể, trả về -1.

Ví dụ, nếu đầu vào là:

const arr = [ 
  [2, 1, 1], 
  [1, 1, 0], 
  [0, 1, 1] 
];

Thì đầu ra nên là:

const output = 4;

Giải thích đầu ra

[ [2, 2, 1], [2, 1, 0], [0, 1, 1] ]

[ [2, 2, 2], [2, 2, 0], [0, 1, 1] ]

[ [2, 2, 2], [2, 2, 0], [0, 2, 1] ]

[ [2, 2, 2], [2, 2, 0], [0, 2, 2] ]

Ví dụ minh họa

Mã thực hiện (BFS đa nguồn):

const arr = [ 
  [2, 1, 1], 
  [1, 1, 0], 
  [0, 1, 1] 
]; 
const timeToRot = (arr = []) => { 
  let fresh = 0; 
  let count = -1; 
  let curr = []; 
  for(let i = 0; i < arr.length; i++){ 
    for(let j = 0; j < arr[i].length; j++){ 
      if(arr[i][j] === 1){ fresh += 1; }; 
      if(arr[i][j] === 2){ curr.push([i, j]); }; 
    }; 
  }; 
  if(!fresh){ return 0; }; 
  while(curr.length > 0){ 
    count += 1; 
    const next = []; 
    const rotten = (i, j) => { 
      arr[i][j] = 2; 
      next.push([i, j]); 
      fresh -= 1; 
    }; 
    for(const [i, j] of curr){ 
      if (arr[i - 1] && arr[i - 1][j] === 1) { rotten(i - 1, j); }; 
      if (arr[i + 1] && arr[i + 1][j] === 1) { rotten(i + 1, j); }; 
      if (arr[i][j - 1] === 1) { rotten(i, j - 1); }; 
      if (arr[i][j + 1] === 1) { rotten(i, j + 1); }; 
    } 
    curr = next; 
  }; 
  return fresh === 0 ? count : -1; 
}; 
console.log(timeToRot(arr));

Đầu ra

Kết quả trong console sẽ là:

4