動態規劃 - 圖論

您是在一個大的N×N個網格（2 < = N < = 100）中，從（1，1）編號到（N，N）。除了（1,1）之外，這些房間中的每個房間都被認爲是「關閉」。你的目標是打開儘可能多的房間。動態規劃 - 圖論

從房間（1,1）開始，這是唯一開始「開」的房間。在一些房間，你會發現燈開關，你可以用它來切換其他房間的狀態;例如在房間（1,1）中可能存在開關，該開關在打開和關閉之間切換房間（1,2）的狀態。您只能通過'on'房間旅行，並且只能從一個房間（x，y）移動到其四個相鄰的鄰居（x-1，y），（x + 1，y），（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 1 2 2 
1 1 1 3 
2 3 3 1 
1 3 1 2 
1 3 2 1 
輸出樣本：

我的工作這個例子自己出去。我發現的最大情況是當你在（1,1）時，你打開（1,2）和（1,3）。然後你去（1,3）然後打開（2,1）。然後你前往（2,1）並開啓（2,2）。但是，由於它仍然是''的，所以你不能得到（2,3）。這給了最多5''房間。

我迄今爲止的做法：

我還以爲這可能是某個動態編程或貪婪的程序。由於N的界限很低，我以爲每次訪問一個節點時，都會更新可能的可訪問地點的數量。也可能有一種方法，您只需嘗試通過打開開關找到地點並嘗試前往該地點。

你能指點我一個算法來解決這個問題，也許一些僞代碼，因爲我對這些類型的問題有點新。

來源

2015-12-13 Prash Som

這可以通過在圖上修改寬度優先搜索來解決。首先，照亮從當前房間可能的所有房間是有意義的。要點亮房間的最大數量，我們必須找到所有從(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

來源

2015-12-13 22:01:49

動態規劃 - 圖論

回答

相關問題