Tiêu diệt kẻ thù trong JavaScript

Mô tả vấn đề

Giả sử chúng ta có một lưới 2D, mỗi ô là tường 'W', kẻ thù 'E' hoặc trống '0' (số không). Chúng ta cần viết một hàm trả về số lượng kẻ thù tối đa có thể tiêu diệt bằng một quả bom.

Quả bom tiêu diệt tất cả kẻ thù trên cùng hàng và cột từ điểm đặt cho đến khi gặp tường (vì tường quá mạnh để phá hủy). Chúng ta cũng chỉ có thể đặt bom ở ô trống.

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

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

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

const output = 3;

Giải thích đầu ra

Đặt bom tại vị trí [1,1] sẽ tiêu diệt 3 kẻ thù - số lượng cao nhất.

Ví dụ minh họa

Mã thực hiện:

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));

Đầu ra

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

3