在NxN網格中查找所有路徑的算法

Question

想象一下坐在NxN網格左上角的機器人。機器人只能在兩個方向上移動：向右和向下。機器人有多少種可能的路徑？

我可以在Google上找到解決此問題的解決方案，但我對解釋並不十分清楚。我試圖清楚地理解如何解決這個問題並在Java中實現的邏輯。任何幫助表示讚賞。

更新：這是一個面試問題。目前，我正在嘗試達到右下角並打印可能的路徑。

Answer 1

我沒有看到你的問題中的障礙跡象，所以我假設沒有。

請注意，機器人需要採取恰好2n的步驟才能到達右下角。因此，它不能再做出更多的動作。

讓我們先從這個私人情況： [尋找到右下角的所有路徑]

機器人可以做完全choose(n,2n)= (2n)!/(n!*n!)路徑：只需要選擇其中的這些2n舉動將是正確的，其餘都是向下[和恰好有n那些]
要生成可能的路徑：剛剛生成所有二進制矢量大小2n的與恰好n 1的。 1表示正確的移動，0表示下移。

現在，讓我們擴大到所有路徑：
首先，您需要選擇的路徑的長度。只需遍歷所有可能性：0 <= i <= 2n，其中i是路徑的長度。在這條路上有max(0,i-n) <= j <= min(i,n)正確的步驟。
要生成的所有可能性，按照此僞代碼：

for each i in [0,2n]: 
    for each j in [max(0,i-n),min(i,n)]: 
    print all binary vectors of size i with exactly j bits set to 1 

注1：打印尺寸的i相設定爲1可能是computationaly膨脹j位的所有二元載體。預計這是因爲機器人的解決方案數量是指數級的。
注2：對於案例i=2n，您得到j in [n,n]，正如我們預計會看到的[我們上面描述的私人案例]。

Answer 2

int N; 
function num_paths(intx,int y) 
{ 
    int[][] arr = new int[N][N]; 
arr[N-1][N-1] = 0; 
for(int i =0;i<N;i++) 
{ 
    arr[N-1][i]=1; 
    arr[i][N-1]=1; 
} 
for(int i = N-2;i>=0;i--) 
{ 
    for(int j=N-2;j>=0;j--) 
    { 
     arr[i][j]= arr[i+1][j]+arr[i][j+1]; 
    } 
} 
return arr[0][0]; 
} 

Answer 3

https://math.stackexchange.com/questions/104032/finding-points-in-a-grid-with-exactly-k-paths-to-them - 請看我的解決方案。看來，這正是你需要的（是的，陳述略有不同，但一般情況下它們都是一樣的）。

Answer 4

public static int computePaths(int n){ 
    return recursive(n, 1, 1);  
} 

public static int recursive(int n, int i, int j){ 
    if(i == n || j == n){ 
     //reach either border, only one path 
     return 1; 
    } 
    return recursive(n, i + 1, j) + recursive(n, i, j + 1); 
} 

要查找所有可能的路徑：仍然使用遞歸方法
。路徑變量在開始時分配爲「」，然後將每個訪問點添加到「路徑」。到達（n，n）點時形成可能的路徑，然後將其添加到列表中。 （1,1）（2,1）（3,1）（4,1）（4,2）（4,3）（4,4）「的每個路徑表示爲一個字符串， 。所有可能的路徑都存儲在一個字符串列表中。

public static List<String> robotPaths(int n){ 
    List<String> pathList = new ArrayList<String>(); 
    getPaths(n, 1,1, "", pathList); 
    return pathList; 
} 
public static void getPaths(int n, int i, int j, String path, List<String> pathList){ 
    path += String.format(" (%d,%d)", i , j); 
    if(i ==n && j == n){ //reach the (n,n) point 
     pathList.add(path); 
    }else if(i > n || j > n){//wrong way 
     return; 
    }else { 
     getPaths(n, i +1, j , path, pathList); 
     getPaths(n, i , j +1, path, pathList); 
    } 
} 

Answer 5

場景：
1.想象有N×N個零索引的矩陣。
2.機器人的初始位置爲左上角，即（N-1，N-1）
3.機器人想要即在（0,0）

解到達右下角：
- - 在任何可能的解決方案中，機器人將移動N個權利步驟和N個向下步驟以達到（0,0），或者我們可以說初始機器人有權移動N個權利步驟和N個向下步驟。
- 當機器人向右移動時，我們將剩餘的右步數減少1，同樣是下移動。
- 在每個位置（除邊界外，它只有一個選項）機器人有兩個選擇，一個是可以下降，另一個是可以向右。
- 當機器人沒有剩下正確的步驟時它會終止。

**下面代碼也具有驅動器的方法的main（），則可以更改的N. N的值可以是> = 1

public class RobotPaths { 

public static int robotPaths(int down, int right, String path) 
{ 
    path = path+ down +","+ right +" "; 
    if(down==0 && right==0) 
    { 
     System.out.println(path); 
     return 1; 
    } 

    int counter = 0; 

    if(down==0) 
     counter = robotPaths(down, right-1, path); 
    else if(right==0) 
     counter = robotPaths(down-1, right, path); 
    else 
     counter = robotPaths(down, right-1, path) + robotPaths(down-1, right, path); 

    return counter; 
} 

public static void main(String[] args) 
{ 
    int N = 1; 
    System.out.println("Total possible paths: "+RobotPaths.robotPaths(N-1, N-1, "")); 

} 

}

Answer 6

這裏是C＃版本（只是（請注意這裏是使用動態編程返回路徑數量的版本（記憶 - 懶惰） - Calculating number of moves from top left corner to bottom right with move in any direction）（您可以參考我的博客瞭解更多詳情：http://codingworkout.blogspot.com/2014/08/robot-in-grid-unique-paths.html）

Tuple<int, int>[][] GetUniquePaths(int N) 
     { 
      var r = this.GetUniquePaths(1, 1, N); 
      return r; 
     } 
     private Tuple<int, int>[][] GetUniquePaths(int row, int column, int N) 
     { 
      if ((row == N) && (column == N)) 
      { 
       var r = new Tuple<int, int>[1][]; 
       r[0] = new Tuple<int, int>[] { new Tuple<int,int>(row, column) }; 
       return r; 
      } 
      if ((row > N) || (column > N)) 
      { 
       return new Tuple<int, int>[0][]; 
      } 
      var uniquePathsByMovingDown = this.GetUniquePaths(row + 1, column, N); 
      var uniquePathsByMovingRight = this.GetUniquePaths(row, column + 1, N); 
      List<Tuple<int, int>[]> paths = this.MergePaths(uniquePathsByMovingDown, 
       row, column).ToList(); 
      paths.AddRange(this.MergePaths(uniquePathsByMovingRight, row, column)); 
      return paths.ToArray(); 
     } 

其中

private Tuple<int, int>[][] MergePaths(Tuple<int, int>[][] paths, 
      int row, int column) 
     { 
      Tuple<int, int>[][] mergedPaths = new Tuple<int, int>[paths.Length][]; 
      if (paths.Length > 0) 
      { 
       Assert.IsTrue(paths.All(p => p.Length > 0)); 
       for (int i = 0; i < paths.Length; i++) 
       { 
        List<Tuple<int, int>> mergedPath = new List<Tuple<int, int>>(); 
        mergedPath.Add(new Tuple<int, int>(row, column)); 
        mergedPath.AddRange(paths[i]); 
        mergedPaths[i] = mergedPath.ToArray(); 
       } 
      } 
      return mergedPaths; 
     } 

單元測試

[TestCategory(Constants.DynamicProgramming)] 
     public void RobotInGridTests() 
     { 
      int p = this.GetNumberOfUniquePaths(3); 
      Assert.AreEqual(p, 6); 
      int p1 = this.GetUniquePaths_DP_Memoization_Lazy(3); 
      Assert.AreEqual(p, p1); 
      var p2 = this.GetUniquePaths(3); 
      Assert.AreEqual(p1, p2.Length); 
      foreach (var path in p2) 
      { 
       Debug.WriteLine("==================================================================="); 
       foreach (Tuple<int, int> t in path) 
       { 
        Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2)); 
       } 
      } 
      p = this.GetNumberOfUniquePaths(4); 
      Assert.AreEqual(p, 20); 
      p1 = this.GetUniquePaths_DP_Memoization_Lazy(4); 
      Assert.AreEqual(p, p1); 
      p2 = this.GetUniquePaths(4); 
      Assert.AreEqual(p1, p2.Length); 
      foreach (var path in p2) 
      { 
       Debug.WriteLine("==================================================================="); 
       foreach (Tuple<int, int> t in path) 
       { 
        Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2)); 
       } 
      } 
     } 

Answer 7

這裏是一個全面實施，無論對於長方形和正方形網格工作。我會讓你想出如何在每條路徑的末端處理多餘的「=>」。

import java.util.Arraylist; 

    public class PrintPath 
    { 
    static ArrayList<String> paths = new ArrayList<String>(); 

    public static long getUnique(int m, int n, int i, int j, String pathlist) 
    { 

     pathlist += ("(" + i + ", " + (j) + ") => "); 

     if(m == i && n == j) 
     {  
      paths.add(pathlist); 
     } 

     if(i > m || j > n) 
     { 
      return 0;    
     } 

     return getUnique(m, n, i+1, j, pathlist)+getUnique(m, n, i, j+1, pathlist); 

    } 

    public static void printPaths() 
    { 
     int count = 1; 
     System.out.println("There are "+paths.size() + " unique paths: \n"); 

     for (int i = paths.size()-1; i>=0; i--) 
     { 

     System.out.println("path " + count + ": " + paths.get(i)); 
     count++; 
     } 

    } 

    public static void main(String args[]) 
    { 
     final int start_Point = 1; 
     int grid_Height = 2; 
     int grid_Width = 2; 

     getUnique(grid_Height, grid_Width, start_Point, start_Point, ""); 
     printPaths(); 

    } 

} 

Answer 8

這是機器人是否可以去4個方向，而不僅僅是2，但低於遞歸解決方案（在Javascript）的作品，我已經試圖使它的清晰越好：

//first make a function to create the board as an array of arrays 
var makeBoard = function(n) { 
    var board = []; 
    for (var i = 0; i < n; i++) { 
    board.push([]); 
    for (var j = 0; j < n; j++) { 
     board[i].push(false); 
    } 
    } 
    board.togglePiece = function(i, j) { 
    this[i][j] = !this[i][j]; 
    } 
    board.hasBeenVisited = function(i, j) { 
    return !!this[i][j]; 
    } 
    board.exists = function(i, j) { 
    return i < n && i > -1 && j < n && j > -1; 
    } 
    board.viablePosition = function(i, j) { 
    return board.exists(i, j) && !board.hasBeenVisited(i,j); 
    } 
    return board; 
}; 


var robotPaths = function(n) { 
    var numPaths = 0; 
    //call our recursive function (defined below) with a blank board of nxn, with the starting position as (0, 0) 
    traversePaths(makeBoard(n), 0, 0); 

    //define the recursive function we'll use 
    function traversePaths(board, i, j) { 
    //BASE CASE: if reached (n - 1, n - 1), count as solution and stop doing work 
    if (i === (n - 1) && j === (n - 1)) { 
     numPaths++; 
     return; 
    } 
    //mark the current position as having been visited. Doing this after the check for BASE CASE because you don't want to turn the target position (i.e. when you've found a solution) to true or else future paths will see it as an unviable position 
    board.togglePiece(i, j); 

    //RECURSIVE CASE: if next point is a viable position, go there and make the same decision 

    //go right if possible 
    if (board.viablePosition(i, j + 1)) { 
     traversePaths(board, i, j + 1); 
    } 

    //go left if possible 
    if (board.viablePosition(i, j - 1)) { 
     traversePaths(board, i, j - 1); 
    } 

    //go down if possible 
    if (board.viablePosition(i + 1, j)) { 
     traversePaths(board, i + 1, j); 
    } 

    //go up if possible 
    if (board.viablePosition(i - 1, j)) { 
     traversePaths(board, i - 1, j); 
    } 

    //reset the board back to the way you found it after you've gone forward so that other paths can see it as a viable position for their routes 
    board.togglePiece(i, j); 
    } 
    return numPaths; 
}; 

一個清潔的版本：

var robotPaths = function(n, board, i, j) { 
    board = board || makeBoard(n), 
    i = i || 0, 
    j = j || 0; 

    // If current cell has been visited on this path or doesn't exist, can't go there, so do nothing (no need to return since there are no more recursive calls below this) 
    if (!board.viablePosition(i, j)) return 0; 
    // If reached the end, add to numPaths and stop recursing 
    if (i === (n - 1) && j === (n - 1)) return 1; 
    // Mark current cell as having been visited for this path 
    board.togglePiece(i, j); 
    // Check each of the four possible directions 
    var numPaths = robotPaths(n, board, i + 1, j) + robotPaths(n, board, i - 1, j) + robotPaths(n, board, i, j + 1) + robotPaths(n, board, i, j - 1); 
    // Reset current cell so other paths can go there (since board is a pointer to an array that every path is accessing) 
    board.togglePiece(i, j); 
    return numPaths; 
} 

所以：

robotPaths(5); //returns 8512 

Answer 9

如果您只需要計算有效路徑：

假設您有一個矩陣n * m矩陣，並將所有單元格設置爲零，將「非限制」單元格設置爲-1。

然後就可以解決動態規劃問題：

// a is a matrix with 0s and -1s 
// n, m are the dimensions 
// M is 10^9-7 incase you have a large matrix 

if (a[0][0] == 0) a[0][0] = 1; 
for (int i = 0; i < n; i++) { 
    for (int j = 0; j < m; j++) { 
     if (a[i][j] == -1) continue; 
     if (i > 0) a[i][j] = (a[i][j] + max(a[i-1][j], 0LL)) % M; 
     if (j > 0) a[i][j] = (a[i][j] + max(a[i][j-1], 0LL)) % M; 
    } 
} 

// answer at lower right corner 
cout << a[n-1][m-1]; 

沒有遞歸或bloaty數據結構，速度極快。

注意：由於被複制而被刪除，但由於這是該主題的最佳主題，因此我從其他地方刪除了我的答案，並將在此處添加此答案。

Answer 10

下面是Java中的代碼，用於計算從NXN矩陣的左上角到右下角的所有可能路徑。

public class paths_in_matrix { 

    /** 
    * @param args 
    */ 
    static int n=5; 
    private boolean[][] board=new boolean[n][n]; 
    int numPaths=0; 
    paths_in_matrix(){ 
     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
       board[i][j]=false; 
      } 
     } 
    } 
    private void togglePiece(int i,int j){ 
     this.board[i][j]=!this.board[i][j]; 
    } 
    private boolean hasBeenVisited(int i,int j){ 
     return this.board[i][j]; 
    } 
    private boolean exists(int i,int j){ 
     return i < n && i > -1 && j < n && j > -1; 
    } 
    private boolean viablePosition(int i,int j){ 
     return exists(i, j) && !hasBeenVisited(i,j); 
    } 
    private void traversePaths(int i,int j){ 
     //BASE CASE: if reached (n - 1, n - 1), count as path and stop. 
     if (i == (n - 1) && j == (n - 1)) { 
      this.numPaths++; 
      return; 
     } 
     this.togglePiece(i, j); 
     //RECURSIVE CASE: if next point is a viable position, go there and make the same decision 

     //go right if possible 
     if (this.viablePosition(i, j + 1)) { 
      traversePaths(i, j + 1); 
     } 
     //go left if possible 
     if (this.viablePosition(i, j - 1)) { 
      traversePaths(i, j - 1); 
     } 

     //go down if possible 
     if (this.viablePosition(i + 1, j)) { 
      traversePaths(i + 1, j); 
     } 

     //go up if possible 
     if (this.viablePosition(i - 1, j)) { 
      traversePaths(i - 1, j); 
     } 

     //reset the board back to the way you found it after you've gone forward so that other paths can see it as a viable position for their routes 
     this.togglePiece(i, j); 

    } 
    private int robotPaths(){ 

     traversePaths(0,0); 
     return this.numPaths; 
    } 
    public static void main(String[] args) { 
     paths_in_matrix mat=new paths_in_matrix(); 
     System.out.println(mat.robotPaths()); 
    } 

}