我想制作一个程序，可以获得从左上到右下方的路径总数，并且会有一些障碍。
例如，如果我有一个像下面的网格迷宫：
@ + + + +
+ + + 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大得多的数字，我想如果我使用没有障碍物的总路径阻挡了总路径障碍物，它应该是带障碍物的总路径。什么地方出了错？谢谢！
阻挡的总路径障碍并不容易计算。它应该是从@开始，向下或向右移动，以$结束并至少传递一个障碍的路径数。
对于这个问题，有两种算法针对不同的数据规模。
1）Inclusion–exclusion principle
障碍物阻挡的总路径=（通过任何一个障碍物的总路径） - （通过任何两个障碍物的总路径）+（通过任何三个障碍物的总路径） - ......
通过任何K障碍物的总路径只能使用枚举来计算。也就是说，将整个障碍的所有子集与K个元素精确对齐，并计算通过它们的路径。
给定K个障碍物，如果有任何两个障碍形成（左，下） - （右，上）对，则没有路径可以通过这些障碍物。否则，我们可以从（左，上）到（右，下）对它们进行排序，计数将是（从@到障碍物1的总路径）*（从障碍物1到障碍物2的总路径）* ... * （从障碍物K到$的总路径）。
最后，从a到b的总路径可以通过nChooseK来解决。多长的日记！
假设存在S个障碍，则该算法的时间复杂度为O（S * 2 ^ S）。
如果您已经知道DP，这会容易得多。如果没有，我会建议你谷歌并先学习它。
简而言之，公式是
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）。
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件事
所以
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数组将是
1 1 1 1 1
1 2 3 0 0
1 0 3 3 3
1 1 4 0 3
1 0 4 4 0
1 1 5 9 9
作为参考，如果您的障碍物非常少，除了上面的包含 - 排除方法之外，可以通过距离开始的距离对障碍物进行排序，以便所有障碍物都不包含在任何先前的障碍物中。现在，考虑我们可以通过它通过的第一个障碍来划分通过某个障碍的每条路径。然后我们可以计算每个障碍物，有多少路径将这个障碍物作为第一个障碍物。一旦我们知道了，只需总结一下，我们就得到了答案。
时间复杂度：O（k ^ 2）其中k是障碍物的数量