ปัญหา Killing Enemy (วางระเบิดฆ่าศัตรูสูงสุด) ใน JavaScript

ปัญหา

กำหนด 2D grid มี 'W' (wall), 'E' (enemy), '0' (empty) หาตำแหน่งวางระเบิดใน empty cell ที่ฆ่าศัตรูได้มากที่สุด (ระเบิดฆ่าทุก enemy ในแถวและคอลัมน์จนกว่าจะเจอ wall)

ตัวอย่าง

grid = [
  ['0','E','0','0'],
  ['E','0','W','E'],
  ['0','E','0','0']
]
output: 3 (วางที่ [1,1] ฆ่าได้ 3 enemies)

ตัวอย่างโค้ด

const arr = [
  ['0', 'E', '0', '0'],
  ['E', '0', 'W', 'E'],
  ['0', 'E', '0', '0']
];

const killEnemy = (arr = []) => {
  let m = arr.length;
  let n = m > 0 ? arr[0].length : 0;
  let result = 0, rows = 0;
  const cols = [];
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (j === 0 || arr[i][j-1] === 'W') {
        rows = 0;
        for (let k = j; k < n && arr[i][k] != 'W'; ++k)
          if (arr[i][k] === 'E') rows += 1;
      }
      if (i === 0 || arr[i-1][j] === 'W') {
        cols[j] = 0;
        for (let k = i; k < m && arr[k][j] != 'W'; ++k)
          if (arr[k][j] === 'E') cols[j] += 1;
      }
      if (arr[i][j] === '0' && rows + cols[j] > result)
        result = rows + cols[j];
    }
  }
  return result;
};

console.log(killEnemy(arr));

ผลลัพธ์

3

คำอธิบาย

Precompute row hits และ col hits สำหรับแต่ละ cell โดยคำนวณใหม่เฉพาะเมื่อเจอ wall หรืออยู่ขอบ

rows: enemies ในแถวเดียวกันระหว่าง walls, cols[j]: enemies ในคอลัมน์ j ระหว่าง walls

Time: O(m*n), Space: O(n) สำหรับ cols array