计算有障碍物的网格中的路径和我的分析

Question

我想编写一个程序，可以获取从左上角到右下点的路径总数，并且会遇到一些障碍。

例如，如果我有一个如下所示的网格迷宫：

@ + + + +
+ + + X X
+ X + + +
+ + + X +
+ X + + X
+ + + + $

它应该告诉我从@到$有9条路径（只能向右或向下移动）。因此，我首先毫无障碍地为网格做了一个小程序，代码如下：

import java.util.*;
import java.math.*;

public class s15 {
    private static long nChooseK(int k, int n) {
        BigInteger numerator = p(k,n);
        BigInteger denominator = p2(k); 
        return numerator.divide(denominator).longValue();
    }

    private static BigInteger p2(int k) {
        BigInteger r = BigInteger.valueOf(1);
        while (k != 0) {
            BigInteger k1 = BigInteger.valueOf(k);
            r = r.multiply(k1);

            k--;
        }
        return r;
    }


    private static BigInteger p(int k, int n) {
        int p;
        int s = 1;
        BigInteger r = BigInteger.valueOf(s);
        for (int i = 0; i <= k-1; i++ ) {
            p = n - i;
            BigInteger p1 = BigInteger.valueOf(p);
            r = r.multiply(p1);
        }
        return r;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();

        System.out.println(nChooseK(x, x+y));
    }



}

然后我首先尝试使用此代码来获取 5*6 迷宫在没有任何障碍的情况下有多少条路径。然后我得到 462，但我必须考虑障碍物，所以我用从每个障碍物到 $ 的路径减去 462，我得到数字：21 70 6 15 10 3，令人惊讶的是，在我使用 462-21-70-6-15-10-3 之后，我得到一个数字是比9大很多，我想如果我用没有障碍物的总路径减去障碍物阻挡的总路径，它应该是有障碍物的总路径。什么地方出了错？谢谢！

Answer 1

dp[i][j]=dp[i-1][j] + dp[i][j-1]...if g[i-1][j] and g[i][j-1] is free.
The points neighbor to start point will be of length 1( ofc valid points)

好吧，投反对票的人..感谢他。

所以这里有 3 件事要记住

我们只能向下或向右移动。所以我们可以从两个点到达 [i,j] 点，如果它们完全空闲的话。这些将是 [i-1,j] 或 [i,j-1].
reacj [i,j] 的路径数等于到达 [i-1,j] 和 [i,j-1] 的路径之和（如果有空的话） .
并且我们需要考虑一些边缘情况，例如 [0,y] 或 [x,0]。

所以

   dp[i][j]=  dp[i-1][j]+dp[i][j-1] if i>=1 & j>=1
              dp[i][j-1]            if i=0  & j>=1
              dp[i-1][j]            if i>=1 & j =0
              1                     if i=0  & j =0
              0                     if x[i][j] is obstacle

答案将是 dp[row-1][col-1]。

Time complexity: O(row*col)
Space complexity: O( row*col)

dp 数组将是

Answer 2

道路障碍物的总数不是那么容易计算的。应该是从@开始，向下或向右移动，到$结束，至少通过一个障碍物的路径数。

对于这个问题，有两种针对不同数据规模的算法。

1) Inclusion–exclusion principle

障碍物阻挡的总路径数=（通过任意一个障碍物的总路径数）-（通过任意两个障碍物的总路径数）+（通过任意三个障碍物的总路径数）- ...

通过任意K个障碍物的总路径只能使用枚举来计算。也就是说，取所有障碍物的所有子集恰好有 K 个元素，并计算通过它们的路径。

给定K个障碍物，如果有任意两个障碍物形成一对（左，下）--（右，上），则没有路径可以通过这些障碍物。否则，我们可以将它们从（左，上）到（右，下）排序，计数将是（从@到障碍物 1 的总路径）*（从障碍物 1 到障碍物 2 的总路径）* ... * （障碍物K到$的总路径）。

最后，a到b的总路径可以通过nChooseK求解。好长的日记！

假设总共有S个障碍物，这个算法的时间复杂度就是O(S*2^S)。

2) Dynamic Programming

如果您已经了解 DP，这会容易得多。如果没有，我建议你google先学习一下。

简而言之，公式是

f[0][0] = 1
if cell (i, j) is an obstacle
  f[i][j] = 0 
else
  f[0][j] = f[0][j - 1]
  f[i][0] = f[i - 1][0]
  f[i][j] = f[i - 1][j] + f[i][j - 1]
Answer = f[N - 1][M - 1]

其中f[i][j]表示从@开始，不经过障碍物，到单元格(i,j)结束的总路径，(N,M)是棋盘的尺寸。

时间复杂度为O(NM)。

Answer 3

作为参考，如果你的障碍物很少，除了上面的Inclusion-Exclusion方法外，还可以根据距离起点的距离对障碍物进行排序，这样所有障碍物都不会包含在任何先前的障碍物中。现在，考虑我们可以将通过某个障碍的每条路径与其通过的第一个障碍分开。然后我们可以计算每个障碍物，有多少路径以这个障碍物作为第一个障碍物。一旦我们知道了，就把它们总结起来，我们就得到了答案。

时间复杂度：O(k^2)，其中 k 是障碍物的数量

计算有障碍物的网格中的路径和我的分析

calculate path in a grid with obstacles and my analysis

java

algorithm

path-finding