Vấn đề
Giả sử, chúng ta có một lưới 2D, mỗi ô là một bức tường 'W', kẻ thù 'E' hoặc trống '0' (số 0). Chúng tôi bắt buộc phải viết một hàm trả về số kẻ thù tối đa mà chúng tôi có thể tiêu diệt chỉ bằng một quả bom.
Quả bom tiêu diệt tất cả kẻ thù trong cùng một hàng và cột từ điểm đã trồng cho đến khi nó chạm vào tường vì bức tường quá mạnh nên không thể bị phá hủy.
Chúng ta cũng phải ghi nhớ rằng chúng ta chỉ có thể đặt bom vào ô trống. Ví dụ:nếu đầu vào của hàm là -
const arr = [ ['0', 'E', '0', '0'], ['E', '0', 'W', 'E'], ['0', 'E', '0', '0'] ];
Sau đó, đầu ra phải là -
const output = 3;
Giải thích đầu ra:
Đặt bom ở [1,1] sẽ tiêu diệt được 3 kẻ thù, đây là mức cao nhất.
Ví dụ
Mã cho điều này sẽ là -
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
Và đầu ra trong bảng điều khiển sẽ là -
3