java - 动态规划 - 图论

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

我自己解决了这个例子。我发现的最大情况是当你在 (1,1) 时，你打开 (1,2) 和 (1,3)。然后您转到 (1,3) 并打开 (2,1)。然后您前往 (2,1) 并打开 (2,2)。但是，您无法到达 (2,3)，因为它仍然处于“关闭”状态。这样最多可以有 5 个“在线”房间。

到目前为止我的方法:

我认为这可能是一个动态规划或贪心规划。由于 N 的界限很低，我想每次访问一个节点时，您都​​会更新可能访问的地方的数量。也可能有一种方法，您只尝试找到打开开关的地方并尝试前往那里。

你能给我指出一个算法来解决这个问题，也许还有一些伪代码，因为我对这些类型的问题有点陌生。

Answer 1

这可以通过修改图的广度优先搜索来解决。首先，从当前房间点亮所有可能的房间是有意义的。要点亮最大数量的房间，我们必须找到从(1,1)可以到达的所有房间(意思是有一条从(1,1)开始的路径经过点亮rooms) 然后 rooms lited up 是可以从这些“可达”房间中的每一个房间点亮的所有房间的 union 。我们一个一个探索可达的房间，找到可以点亮的房间。这可能会为我们提供更多可达的房间。

完整的伪代码是:

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