หาเส้นตรงของ 1 ยาวที่สุดในเมทริกซ์ (Horizontal, Vertical, Diagonal) ด้วย JavaScript

ปัญหา

ได้รับเมทริกซ์ไบนารี ให้หาเส้นต่อเนื่องของ 1 ที่ยาวที่สุด (แนวนอน, แนวตั้ง, แนวทแยง, แนวทแยงตรงข้าม) และคืนความยาว

ตัวอย่าง

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

เส้นยาวสุดคือแนวทแยงจาก arr[0][1] ถึง arr[2][3] ความยาว 3

โค้ดตัวอย่าง (Dynamic Programming)

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; // horizontal 
        dp[i][j][1] = i > 0 ? dp[i - 1][j][1] + 1 : 1; // vertical 
        dp[i][j][2] = (i > 0 && j > 0) ? dp[i - 1][j - 1][2] + 1 : 1; // diagonal 
        dp[i][j][3] = (i > 0 && j < cols - 1) ? dp[i - 1][j + 1][3] + 1 : 1; // anti-diagonal 
        res = Math.max(res, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3]); 
      } 
    } 
  } 
  return res; 
}; 
console.log(longestLine(arr));

ผลลัพธ์

3