Skip to content

Instantly share code, notes, and snippets.

@bemusementpark
Last active March 4, 2019 13:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bemusementpark/d24538b9f0c74c385adfda348e546d97 to your computer and use it in GitHub Desktop.
Save bemusementpark/d24538b9f0c74c385adfda348e546d97 to your computer and use it in GitHub Desktop.
A solution to the flood-fill related question described here: https://youtu.be/IWvbPIYQPFM
fun countMaxFloodFill(colors: Array<IntArray>): Int {
var best = 0
val counts = arrayOfNulls<AtomicInteger?>(colors.size)
colors.forEachIndexed { y, rows ->
rows.forEachIndexed { x, color ->
// get the current count from the neighbour above or to the left of the current cell if either have the same color.
// If above and left have the same color, check if they are connected, if they are not, we can connect them and add them together.
val leftIsSameColor = colors.getOrNull(y)?.getOrNull(x - 1)
val aboveIsSameColor = colors.getOrNull(y - 1)?.getOrNull(x)
val intRef = when {
leftIsSameColor && aboveIsSameColor -> {
if(counts[x - 1] !== counts[x]) {
counts[x].addAndGet(counts[x - 1].get())
counts[x - 1] = counts[x]
counts[x]
} else {
if(counts[x] > counts[x - 1]) counts[x] else counts[x - 1]
}
}
leftIsSameColor -> counts[x - 1]
aboveIsSameColor -> counts[x]
else -> null
}
// Increment it or if this is a new region set it to 1.
best = intRef?.incrementAndGet() ?: 1
counts[x] = intRef ?: AtomicInteger(1)
}
}
return best
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment