Dynamic Programming - Graph Theory

Question

You are in a large NxN grid with (2 <= N <= 100), numbered from (1, 1) to (N,N). Each of these rooms except (1,1), is considered to be turned 'off'. Your goal is to turn on as many rooms as possible.

You start in room (1,1), the only room that is initially 'on'. In some rooms, you will find light switches that you can use to switch the state of other rooms; for example there might be a switch in room (1,1) that toggles the state of room (1,2) between on and off. You can only travel through 'on' rooms, and can only move from a room (x,y) to its four adjacent neighbors (x−1,y), (x+1,y), (x,y−1) and (x,y+1) (or possibly fewer neighbors if this room is on the boundary of the grid).

Find the maximum number of rooms you can turn 'on'.

An example: The first line of input contains integers N and M (1≤M≤20,000).

The next M lines each describe a single light switch with four integers x, y, a, b, that a switch in room (x,y) can be used to toggle the state in room (a,b). Multiple switches may exist in any room, and multiple switches may toggle the state of any room.

Output: A single line giving the maximum number of rooms you can turn 'on'.

SAMPLE INPUT:
3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1
SAMPLE OUTPUT:

5

I worked this example out on my own. The max case I found is when you are in (1,1), you turn on (1,2) and (1,3). You then go to (1,3) and turn on (2,1). You then head to (2,1) and turn on (2,2). Yet, you cannot get to (2,3) as it is still turned 'of'. That gives a max of 5 'on' rooms.

My approach so far:

I have thought that this might either be a dynamic programming or greedy program. Since the bounds on N are quite low, I was thinking that each time you visit a node, you update the number of possible visitable places. There also may be an approach where you solely try to find the places with turn on switches and try to head there.

Could you point me to an algorithm to solve this problem and maybe some pseudocode as I am a bit new to these types of questions.

Sagar Jha · Accepted Answer · 2015-12-13 22:01:49Z

This can be solved by a modified breadth-first search on graphs. First of all, it makes sense to lit up all the rooms possible from the current room. To lit up the maximum number of rooms, we have to find all the rooms that can be reached from (1,1) (meaning that there is a path from (1,1) going through lit up rooms) and then the rooms lit up is the union of all the rooms that can be lit up from each of these "reachable" rooms. We explore the reachable rooms one by one and find the rooms that can be lit up. This can potentially give us more reachable rooms.

The complete pseudo-code is :

queue Q
Q.push (1,1) // room (1,1) reachable
set litupRooms
litupRooms.push(1,1) // room (1,1) is lit up
set visitedRooms
while (Q is not empty)
  room r = Q.pop ()
  if r is in visitedRooms
    continue
  add r to visitedRooms
  for every room that can be lit up from r
    if it is already lit up
      continue
    add it to litupRooms 
    push it to Q if it is adjacent to a room already visited
  for every adjacent room of r
    push it to Q if it is lit up and not visited
return the size of litupRooms

Collectives™ on Stack Overflow

Dynamic Programming - Graph Theory

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related