查找網格中的路徑故障

我想查找棋盤上左上角和右下角單元格之間的路徑數量。我只能移動到相鄰的右邊和相鄰的底部細胞。這樣我可以有最多2個不相交的簡單路徑。我正在使用遞歸方法。查找網格中的路徑故障

private void processMatrix() 
{ 
    if(matrix[0][0]!=1 || matrix[0][0]!=matrix[ROWS-1][COLUMNS-1]) 
     System.out.println("No Path Exists between bottom right and top left cells"); 
    int row=0; 
    int col=0; 
    traverse(row,col); 
} 

    private boolean traverse(int row, int col) 
{ 
    path.add(new Point(row,col)); 

    if(row+1<ROWS) 
    { 
     if(matrix[row+1][col]==0) 
     { 
      return false; 
     } 
     if(matrix[row+1][col]==1) 
     { 
      traverse(row+1,col); 
     } 
    } 
    if(col+1<COLUMNS) 
    { 
     if(matrix[row][col+1]==0) 
     { 
      return false; 
     } 
     if(matrix[row][col+1]==1) 
     { 
      traverse(row,col+1); 
     } 
    } 
    if(col==COLUMNS-1 && row==ROWS-1) 
     return true; 
    return false; 
}

但是用這段代碼我只能遍歷下三角矩陣。當我逆轉遍歷（）函數中塊的順序時，我只能遍歷上三角矩陣中的路徑。無法弄清楚什麼是錯的。我也想檢測相交的路徑。請幫忙。

編輯： 該矩陣由0和1組成。如果通過僅包含1的相鄰單元連接，則存在路徑。換句話說，路徑將是1的鏈。

來源

2013-11-24 Madeyedexter

你似乎用你的代碼過分複雜。如果你的矩陣是0和1，使用布爾代替int。非相交路徑似乎有點愚蠢，因爲所有路徑在出租車幾何中都是同等有效的。下面是找到號碼的所有路徑的簡單的解決方案，它會告訴你如何與System.out的打印塊的工作：

int rows = 9; 
int columns = 8; 
boolean[][] matrix = new boolean[rows][columns]; 
for (boolean[] arr : matrix) {/* Set values of matrix such that true = can pass thru that space, false = space blocked */ 
    Arrays.fill(arr, true); 
} 
matrix[4][6] = false; 
matrix[2][5] = false; 
int[][] paths = new int[rows][columns];//number of paths reaching each space in i steps 
paths[0][0] = 1; //Starting space 
for (int i = 0; i < rows + columns - 2; i++) {//Taxicab distance is always x+y, i = distance travelled so far 
    int[][] newPaths = new int[rows][columns]; //number of paths reaching each space in i+1 steps 
    for (int x = i >= columns ? i - columns + 1 : 0; x <= i && x < rows;) { //x is traditionally columns but it doesn't matter 
     int y = i - x; //if statement is x declaration ensures that this is < columns 
     int newX = x + 1; //will be used repeatedly 
     int newY = y + 1; //will be used repeatedly 
     if (newX < rows && matrix[newX][y]) newPaths[newX][y] += paths[x][y]; 
     if (newY < columns && matrix[x][newY]) newPaths[x][newY] += paths[x][y]; 
     x = newX; 
    } 
    paths = newPaths; 
    for (int x = 0; x < rows; x++) { //optional, show the algorithm at work 
     for (int y = 0; y < columns; y++) { 
      int r = paths[x][y]; 
      System.out.print(r); 
      if (r < 100) System.out.print(" "); 
      if (r < 10) System.out.print(" "); 
     } 
     System.out.println(); 
    } 
    System.out.println(); 
} 
System.out.println(paths[rows - 1][columns - 1]); //result

如果你想確定是一個路徑是否存在，是否替換INT [] []路徑與布爾[] []路徑並相應地更改操作。

來源

2013-11-24 20:20:35 Vitruvius

這是一個基本的動態規劃問題。

設dp[R][C]爲行R和列C（1索引）從左上單元格到單元格的路徑數。

的初始值（當R或C是1）：
- dp[R][1] = 1如果matrix[i][1]具有用於i = 1..R值1，否則dp[R][1] = 0。
- dp[1][C] = 1如果matrix[1][j]對於j = 1..C具有值1，否則dp[1][C] = 0。
然後dp[R][C] = dp[R-1][C] + dp[R][C-1]如果matrix[R][C] = 1，否則dp[R][C] = 0（對於R，C> = 2）

，這是它。這個想法背後的直覺是，如果我們知道我們可以通過N條不同的道路到達R-1行C列的單元格，那麼如果我們下去一次，我們將得到N條到達單元格[R，C]的不同道路。類似於從單元[R，C-1]到[R，C]的右側。

最後，答案在dp[N][M]，其中N和M是矩陣的維數。

來源

2013-11-24 23:38:52 yasen

查找網格中的路徑故障

回答

相關問題