Tìm dòng 1s dài nhất trong ma trận trong JavaScript

Giả sử, chúng ta có một ma trận nhị phân (một mảng chỉ chứa 0 hoặc 1) như thế này -

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

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một ma trận như vậy làm đối số đầu tiên và duy nhất.

Nhiệm vụ của hàm của chúng ta là tìm dòng dài nhất trong số các dòng liên tiếp trong ma trận và trả về số lượng 1s trong đó. Đường có thể nằm ngang, dọc, chéo hoặc chống chéo.

Ví dụ, đối với mảng trên, đầu ra phải là -

const output = 3

bởi vì dòng dài nhất là dòng bắt đầu từ arr [0] [1] và kéo dài theo đường chéo lên đến -

arr[2][3]

Ví dụ

Mã cho điều này sẽ là -

const arr = [
   [0,1,1,0],
   [0,1,1,0],
   [0,0,0,1]
];
const longestLine = (arr = []) => {
   if(!arr.length){
      return 0;
   }
   let rows = arr.length, cols = arr[0].length;
   let res = 0;
   const dp = Array(rows).fill([]);
   dp.forEach((el, ind) => {
      dp[ind] = Array(cols).fill([]);
      dp[ind].forEach((undefined, subInd) => {
         dp[ind][subInd] = Array(4).fill(null);
      });
   });
   for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
         if (arr[i][j] == 1) {
            dp[i][j][0] = j > 0 ? dp[i][j - 1][0] + 1 : 1;
            dp[i][j][1] = i > 0 ? dp[i - 1][j][1] + 1 : 1;
            dp[i][j][2] = (i > 0 && j > 0) ? dp[i - 1][j - 1][2] + 1 : 1;
            dp[i][j][3] = (i > 0 && j < cols - 1) ? dp[i - 1][j + 1][3] + 1 : 1;
            res = Math.max(res, Math.max(dp[i][j][0], dp[i][j][1]));
            res = Math.max(res, Math.max(dp[i][j][2], dp[i][j][3]));
         };
      };
   };
   return res;
};
console.log(longestLine(arr));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

3