UVa 10309

From Algorithmist
Jump to navigation Jump to search


Summary[edit]

You are given a 10x10 grid of light bulbs, each one of them is either switched of or on. Each light bulb has a switch on the same cell in the grid cell. Unfortunately, these switches don't work as expected. Whenever a switch is pressed the bulb on the same cell along with the 4 neighboring cells are toggled. We need to find the minimum number of switches pressed in order to turn off the whole grid.

  ###      #O#
  ###  ->  OOO
  ###      #O#

  ###      #O#
  OOO  ->  ###
  ###      #O#

Explanation[edit]

This problem is solved using complete search technique. Notice that each bulb can be toggled by 3 switches on the same row and 1 switch on the upper row and another one on the lower row, keep this in mind as we will use it later. Our solution has three steps: 1. For the first row try all 2^10 possible combinations of switches. We expect to have some switches turned on after this step. 2. For the rest of the rows, toggle switch (i, j) if (i-1, j) is switched on, this means toggle any switch if the bulb above it (in the previous row is turned on). This step insures that all bulbs will be turned off using the switch in the next row, except the last row, as there is no next row. 3. Check the bulbs in the last row, if all bulbs are turned off, then the current solution if valid, if any of the bulbs is on, this solution is not valid. Keep track of the number of switches toggled in each solution, and the final result is their minimum value;

Gotchas[edit]

  • Switches on the edges don't toggle 5 bulbs.
  • Don;t forget to print the name of the case in the output.

Notes[edit]

  • This problem is solved in O(2^n), where n = 10 (size of first row).

Implementations[edit]

  • Using bits to represent bulbs is better since it has 2 states and is much faster than using booleans or characters.

Input[edit]

CASE_1
OO##OOOOO#
###OO###OO
##OO#####O
#OO#OO#OOO
#O#OO####O
OO###OO##O
OO#O#####O
O###OO#O#O
OO#OO#O##O
##O##O##OO
CASE_2
O##OOO##OO
#OO####O##
O##OO###OO
##OOOOO#O#
O###OO##OO
#O##OO#O##
O#O####OOO
#OOOO###OO
OOO##OOOOO
##OOO##O##
CASE_3
OO########
##########
##########
##########
##########
##########
##########
##########
##########
##########
CASE_4
OOOO####O#
#OOO#OOOO#
OOOO##O#OO
O#O###O#O#
OOO#OO#OO#
O###OO####
OOO#O#OO##
OO###O####
#OO#OO##OO
O#OOOO###O
CASE_5
OO##O###OO
#O#OOO##O#
####O###O#
OOOOO#####
#O####OO##
##OO##O##O
#O####O#O#
#OOO#OO##O
###O##O#OO
####OO#O#O

Output[edit]

CASE_1 50
CASE_2 45
CASE_3 39
CASE_4 49
CASE_5 48