Skip to content

Instantly share code, notes, and snippets.

@nthung2112
Created December 5, 2023 09:07
Show Gist options
  • Save nthung2112/029b145c1a6bb23cd2ed397c081d422d to your computer and use it in GitHub Desktop.
Save nthung2112/029b145c1a6bb23cd2ed397c081d422d to your computer and use it in GitHub Desktop.
function countShips(B) {
const result = [0, 0, 0];
const map = B.map(row=>row.split(''));
const n = map.length;
const m = map[0].length;
for (let row = 0; row < n; row++) {
for (let col = 0; col < m; col++) {
if (map[row][col] === '#') {
map[row][col] = '.';
const count = getSizeOfShip(map, row, col);
if (count <= 3) {
result[count - 1]++;
}
}
}
}
return result;
}
function isShipCell(map, row, col) {
return row >= 0 && row < map.length && col >= 0 && col < map[0].length && map[row][col] === '#';
}
function getSizeOfShip(map, row, col) {
const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const queue = [[row, col]];
let sizeOfShip = 1;
for (let i = 0; i < queue.length; i++) {
const [currentRow,currentCol] = queue[i];
for (let j = 0; j < dirs.length; j++) {
const [dx,dy] = dirs[j]
const x = currentRow + dx;
const y = currentCol + dy;
if (isShipCell(map, x, y)) {
map[x][y] = '.';
sizeOfShip++;
queue.push([x, y]);
}
}
}
return sizeOfShip;
}
const B1 = [".##.#", "#.#..", "#...#", "#.##."];
console.log(countShips(B1).join(','));
const B2 = [".#..#", "##..#", "...#."];
console.log(countShips(B2).join(','));
const B3 = ["##.", "#.#", ".##"];
console.log(countShips(B3).join(','));
const B4 = ["...", "...", "..."];
console.log(countShips(B4).join(','));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment