查找表中的路径数

Question

Tere是一张大小为R×C的表格; R行和C列.该表的子矩形被阻止.我们只能向右或向下移动.在没有通过被阻挡的子矩形的情况下,从左上角单元格到右下角单元格的路径数是多少？

我的方法: 计算行r2 C = {0到c1-1}的路径和行r1的路径C = {c2 + 1,C}

r1,c1,r2和c2,左上角的单元格和下面的单元格 - 被阻止的矩形的正确单元格.

Cal Calculate C(n,k)

我的代码:

int R = in.nextInt()-1;
int C = in.nextInt()-1;
int r1 = in.nextInt()-1;
int c1= in.nextInt()-1;
int r2 = in.nextInt()-1;
int c2 = in.nextInt()-1;
long ans=0;
long temp=0;
temp+= Cal(R-r2+C-c1,C-c1);
for(int i=0;i<c1 && r2!=R;i++){
    ans+=Cal(i+r2,r2)*(Cal(R-r2+C-i,C-i)-temp);
}
temp=0;

temp+=Cal(r1+c2,r1);

for(int i=c2+1;i<=C;i++){
ans+= (Cal(i+r1,r1)-temp)*Cal(C-i+R-r1,C-i);

}
System.out.println(ans);

我没有得到上述算法的正确答案.如果我做错了,请帮助我.

Sample input:
8 12
5 5 8 8    ANS:7008

Answer 1

我发现很难理解你的算法的描述，所以我不知道如何提供帮助。但是，我认为查找路径数量的一种方法可能是从总可能路径中减去包含子矩形中的单元格的路径。

包含特定单元格的路径数等于从左上角到该单元格的路径数乘以从该单元格到右下角的路径数。由于您只能向下或向右移动，因此考虑子矩形的左列和顶行就足以解释所有内容。

如果您从子矩形的左上角开始，则可以按照以下示例进行操作（ABCDEF构成子矩形）：

start   X     X     X     X
  X     A     B     C     X
  X     D     E     F     X
  X     X     X     X    end

The sum of paths that include A,B,C,D,E or F equals:
   Paths to A * Paths from A to end = 2 choose 1 * 5 choose 2                   = 20
 + (Paths to cell above B) * Paths from B to end = 1 * 4 choose 2               = 6
 + (Paths to cell above C) * Paths from C to end = 1 * 3 choose 1               = 3
 + (Paths to cell left of D) * Paths from D to end = 1 * 4 choose 1             = 4

Solution equals: total paths - the number of paths that include A,B,C,D,E or F 
= 7 choose 3 - (20 + 6 + 3 + 4)                                                 = 2

JavaScript 代码：

start   X     X     X     X
  X     A     B     C     X
  X     D     E     F     X
  X     X     X     X    end

The sum of paths that include A,B,C,D,E or F equals:
   Paths to A * Paths from A to end = 2 choose 1 * 5 choose 2                   = 20
 + (Paths to cell above B) * Paths from B to end = 1 * 4 choose 2               = 6
 + (Paths to cell above C) * Paths from C to end = 1 * 3 choose 1               = 3
 + (Paths to cell left of D) * Paths from D to end = 1 * 4 choose 1             = 4

Solution equals: total paths - the number of paths that include A,B,C,D,E or F 
= 7 choose 3 - (20 + 6 + 3 + 4)                                                 = 2

输出：

function f(Rows,Cols,r1,c1,r2,c2){
  var r = Rows - r1,
      total = C(Rows + Cols - 2,Rows - 1),
      s = C(r1 + c1 - 2,r1 - 1) * C(Cols - c1 + r,r);

  if (c2 > c1 && r1 > 1){
    for (var i=c1+1; i<=c2; i++){
      s += C(i + r1 - 3,i - 1) * C(Cols - i + r,r);
    }
  }

  if (r2 > r1 && c1 > 1){
    for (var i=r1+1; i<=r2; i++){
      s += C(i + c1 - 3,i - 1) * C(Rows - i + Cols - c1,Rows - i);
    }
  }

  return total - s;
}

function C(n,k){if(k==0||n==k)return 1;var p=n;for(var i=2;i<=k;i++)p*=(n+1-i)/i;return p}