动态规划-图论

Question

您是在一个大型NxN网格中，(2 <= N <= 100)，编号从(1，1)到(N，N)。除(1,1)外，所有这些房间都被视为“关闭”。你的目标是打开尽可能多的房间。 您从房间(1,1)开始，这是最初“打开”的唯一房间。在某些房间中，您会发现可以用来切换其他房间的状态的灯开关；例如，房间(1,1)中可能有一个开关，它在打开和关闭之间切换房间(1,2)的状态。您只能通过“on”房间，并且只能从一个房间(x，y)移动到它的四个相邻邻居(x，y，x+1，y)，(x，y−1)和(x，y−1)和(x，y+1) (如果这个房间位于网格边界，则可能更少)。 找到你可以打开的房间的最大数量。 例如:第一行输入包含整数N和M (1≤M≤20,000)。 下一个M行分别描述一个具有四个整数x，y，a，b的光开关，即房间(x，y)中的开关可以用来切换房间(a，b)中的状态。多个开关可以存在于任何房间，多个开关可以切换任何房间的状态。 输出:一个单行，给出你可以打开的房间的最大数量。 样本输入： 3 6 1 1 1 2 2 2 1 1 1 3 3 3 1 1 3 1 1 1 样本输出： 5

我自己解决了这个例子。我发现的最大情况是，当你在(1,1)，你打开(1,2)和(1,3)。然后转到(1,3)并打开(2,1)。然后前往(2,1)并打开(2,2)。然而，你不能达到(2,3)，因为它仍然是“of”。最多5英寸的房间。

到目前为止，我的方法：

我认为这可能是一个动态规划或贪婪的程序。由于N的界限很低，所以我认为每次访问一个节点时，都会更新可能访问的位置的数量。也可能有一种方法，你只想找到打开开关的地方，然后尝试去那里。

你能告诉我一个解决这个问题的算法吗?也许是一些伪码，因为我对这类问题有点陌生。

Answer 1

这可以通过修改的宽度优先搜索图来解决。首先，给点亮了所有可能来自当前房间的房间是有意义的。要照亮房间的最大数量，我们必须找到所有可以从(1,1)到达的房间(这意味着有一条从(1,1)条通道穿过亮起的房间)，然后，所有可以从这些“可达”房间中点燃的房间一起点亮。我们一个接一个地探索可到达的房间，找到可以点亮的房间。这可能会给我们提供更多可到达的房间。

完整的pseudo-code是：

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