Connection Status:
Competition Arena > CrazySwitches

CrazySwitches

SRM 291 · 2006-02-21 · by Olexiy

SRM 291 · 2006-02-21 · by Olexiy · Brute Force, Graph Theory
Class Name: CrazySwitches
Return Type: int
Method Name: minimumActions
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You are in a house where the light in each room is controlled by a switch that might be located in a different room. Initially, the light in the first room is on, and the lights in all the other rooms are off.

You are currently in the first room and your goal is to end up in the last room, with all the lights in the house off except the light in the last room. You can move directly from any room to any other room, and you can turn any of the switches that are located in your current room. However, you may never enter a dark room or turn off the light in your current room.

You are given a int[] switches describing the locations of the light switches. The light switch for room i is located in room switches[i]. Rooms have 0-based indices. Return the minimal number of moves required to complete your task, or -1 if it is impossible. Only moving from one room to another counts as a move (turning a switch is not counted).

Constraints

  • switches will contain between 2 and 16 elements, inclusive.
  • Each element in switches will be between 0 and the number of elements in switches - 1, inclusive.
Examples
0)
{1, 0}
Returns: 1

You can switch on the light in the last room, move into the last room and switch off the light in the first room.

1)
{0, 1}
Returns: -1

You can't do anything.

2)
{1, 2, 0}
Returns: 3

You can switch on the light in the last room, move into the last room, switch on the light in the second room, move into the second room, switch off the light in the first room, move into the last room and switch off the light in the second room.

3)
{4, 4, 3, 0, 5, 2}
Returns: 7
4)
{7, 11, 1, 12, 6, 3, 0, 2, 6, 0, 0, 5, 9}
Returns: 15

Submissions are judged against all 119 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CrazySwitches with a public method int minimumActions(vector<int> switches) · 119 test cases · 2 s / 256 MB per case

Submitting as anonymous