Một virus zombie nguy hiểm đang lan rộng ở các thành phố số. Chúng ta làm việc tại CDC số, nhiệm vụ xem bản đồ thành phố và xác định khu vực bị nhiễm virus để quân đội số biết ném bom đâu.
Đây là zombie số mới: chỉ di chuyển theo chiều dọc và ngang, chỉ lây lan sang số giống chúng.
Cho mảng hai chiều chứa số. Bệnh nhân số 0 luôn ở góc tây bắc (phần tử [0][0]) và dịch lan từ đó sang các ô khác bằng cách đi lên, xuống, trái, phải.
Tạo hàm trả về bản đồ (mảng 2 chiều) đánh dấu khu vực nhiễm là 1, không nhiễm là 0. Tức là tìm tất cả phần tử matrix cùng giá trị [0][0] có thể đến được từ [0][0] chỉ đi lên/xuống/trái/phải - không bước vào ô giá trị khác.
Ví dụ
Dưới đây là đoạn code:
const arr = [
[9, 1, 2, 3, 4, 1, 2, 9],
[9, 9, 9, 2, 1, 5, 9, 9],
[9, 2, 9, 3, 7, 9, 1, 9],
[6, 9, 9, 9, 0, 9, 2, 9],
[5, 4, 3, 9, 9, 9, 4, 9],
[9, 3, 9, 5, 8, 9, 9, 9],
[9, 9, 9, 9, 9, 9, 7, 9],
[9, 9, 1, 2, 3, 9, 8, 9]
];
const findZombies = arr => {
let i, j, result = [],
zombie = arr[0][0],
tree = {};
const chance = ([i, j]) => {
if (!tree[i] || !tree[i][j]) return;
result[i][j] = 1;
var temp = tree[i][j];
tree[i][j] = undefined;
temp.forEach(chance);
}
for (i = 0; i < arr.length; i++) {
result.push([]);
for (j = 0; j < arr[i].length; j++) {
result[i].push(0);
if (arr[i][j] !== zombie) continue;
if (!tree[i]) tree[i] = {};
tree[i][j] = [[i, j - 1], [i, j + 1], [i - 1, j], [i + 1, j]].filter(([x, y]) => arr[x] && arr[x][y] === zombie);
};
};
chance([0, 0]);
return result;
};
console.log(findZombies(arr));Kết quả console:
[ [ 1, 0, 0, 0, 0, 0, 0, 1 ], [ 1, 1, 1, 0, 0, 0, 1, 1 ], [ 1, 0, 1, 0, 0, 1, 0, 1 ], [ 0, 1, 1, 1, 0, 1, 0, 1 ], [ 0, 0, 0, 1, 1, 1, 0, 1 ], [ 1, 0, 1, 0, 0, 1, 1, 1 ], [ 1, 1, 1, 1, 1, 1, 0, 1 ], [ 1, 1, 0, 0, 0, 1, 0, 1 ] ]