Skip to content

Instantly share code, notes, and snippets.

@ambethia
Created August 16, 2022 18:47
Show Gist options
  • Save ambethia/23177038ea3f02d3bcfd83827d0df94a to your computer and use it in GitHub Desktop.
Save ambethia/23177038ea3f02d3bcfd83827d0df94a to your computer and use it in GitHub Desktop.
const map = [
[1, 0, 1, 0, 0, 0, 1, 1, 1, 1],
[0, 0, 1, 0, 1, 0, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
[0, 1, 0, 1, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 1, 1, 1, 0],
[1, 0, 1, 0, 1, 0, 0, 1, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
]
// const map = [
// [1, 0, 1, 0],
// [0, 0, 1, 0],
// [0, 0, 1, 1],
// [0, 0, 0, 0],
// ]
class Queue {
constructor() {
this.data = []
}
enqueue(element) {
this.data.push(element)
}
dequeue() {
return this.data.shift()
}
}
function countIslands(map) {
const islands = []
const visited = new Set()
const height = map.length
const width = map[0].length
function isUnseen(x, y) {
return !visited.has([x, y].toString())
}
function visit(x, y) {
visited.add([x, y].toString())
}
function bfsCount(x, y) {
let count = 1
visit(x, y)
const queue = new Queue()
let current = [x, y]
while (current) {
const cx = current[0]
const cy = current[1]
for (let dx = -1; dx <= 1; dx++) {
for (let dy = -1; dy <= 1; dy++) {
const nx = cx + dx
const ny = cy + dy
if (
!(dx === 0 && dy === 0) &&
nx >= 0 &&
nx < width &&
ny >= 0 &&
ny < height
) {
if (isUnseen(nx, ny) && map[ny][nx] > 0) {
visit(nx, ny)
queue.enqueue([nx, ny])
count++
}
}
}
}
current = queue.dequeue()
}
return count
}
for (let y = 0; y < map.length; y++) {
for (let x = 0; x < map[y].length; x++) {
if (map[y][x] > 0 && isUnseen(x, y)) {
const size = bfsCount(x, y)
islands.push(size)
}
}
}
return islands.sort((a, b) => a - b)
}
console.log(countIslands(map))
console.log('----')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment