查找矩陣中是否有路徑？

Question

給定一個大小爲N的方陣。它由元素0,1和2組成。我們必須確定是否存在從位置[0,0]到[N-1，N-1]的任何路徑。我們可以向上，向下，向左，向右四個方向移動。

我們只能移動0。 1是閉鎖元件，，而2是可移動的塊，如果可能的話可以移動以形成路徑。

我能夠通過遞歸解決簡單的迷宮問題，但我應該如何處理可移動的塊。

Example 
Matrix : 
0 1 1 0 1 
0 2 0 0 1 
1 0 1 0 1 
1 1 2 0 0 

這裏如果你知道如何解決簡單的迷宮，我們可以做出的路徑，如果我們從位置[​​1,1]到[2,1]

Answer 1

移動2，這不應該是一個很難的問題。解決方案應該只是簡單迷宮的延伸。

您可以使用BFS或DFS來解決問題。這裏的技巧是擴展原始狀態（x，y），當前位置爲（x，y，x0，y0，x1，y1，xn-1，yn-1），其中（xi，yi） ith移動塊。此外，除了4個方向的移動（向上，向下，向左，向右移動），還應該有4個可能的移動動作，左移左移（如果存在），向上移動，向右移右，向下阻擋。因此有8種可能的行動從一個國家轉移到另一個國家。

希望這會有所幫助。