Editorial for VMSS '15 #2 - Tomb Robbing


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: kobortor

Simple problem asking us to count the number of "rooms" on the map. The simplest method to check for this is to convert the map into a 2D boolean array and use a recursive search. In the recursive function, we move up, down, left or right from the current spot if the targeted block is clear. Using this, we can mark every "clear" block in a room once visited to make sure each room is only visited once.

Final Complexity: \mathcal O(RC)


Comments

There are no comments at the moment.