两点间方格路径总数

题目描述：一个长方形，由m*n个大小相同的个子组成，左上角为坐标零点（0,0），求其中任意一点A（x1, y1）到点B（x3， y3）的路径总条数，认为x1<=x3,y1<=y3

分析：这题可以采用动态规划的思想，假设k[a][b]代表从（0,0）到（a，b）的路径的总条数，则有

递推公式：k[x][y] = k[x+1][y] + k[x][y+1]，也就是从（x，y）到目的地的总路径数等于先向右（x+1, y）的总路径数k[x][y+1]，与先向下k[x][y+1]路径总数之和

边界条件：如图，B点（终点）所在的行和列均只有一个选择，也就是k[row][] 与 k[][col]等于1

C++代码如下：
#include <iostream>
#include <vector>
using namespace std;

int getPathNum( int row, int col )
{
	if ( row == 0 && col == 0 )//两点重合
		return 0;
	else if ( row == 0 || col == 0 )   //当两点在同一行或者同一列
		return 1;
	vector< vector<int> > path( row + 1 );
	for ( int i=0; i<=row; i++ )
		path[i].resize( col + 1 );
	for ( int i=0; i<row; i++ )
		path[i][col] = 1;
	for ( int i=0; i<col; i++ )
		path[row][i] = 1;
	path[row][col] = 0;
        for ( int i=row-1; i>=0; i-- )//从除边界行以外的最后一行开始，从右至左计算每个点		
		for ( int j=col-1; j>=0; j-- )
			path[i][j] = path[i][j+1] + path[i+1][j];
	return path[0][0];
}

int main()
{
	int x1 = 1, y1 = 1;
	int x3 = 3, y3 = 3;
	cout<<getPathNum( x3-x1, y3-y1 )<<endl;
	return 0;
}

输出：6

当x3=y3=4时，输出20

观察图可知从B点开始，以B点为终点，则x1=y1=1，x2=y2=3时，相当于B点和C点的位置，此时C点等于6，同样20也可以观察出来

程序解释：

（1）首先判断两点是否在同一行或者同一列，若在则只有一条路，返回1；若两点重合则返回0；

（2）建立二维矩阵[row+1, col+1]，同时给定边界条件，行为row或者列为col的均为1，终点（row，col）为0；

（3）根据递推公式k[x][y] = k[x+1][y] + k[x][y+1]，自下向上，自右往左分别计算每一行

（4）最后返回矩阵中[0][0]即为两点之间的路径总数

先假设如图点A与点C之间存在一个障碍点B（不能够经过），求A到C之间的路径总数，则计算思想如下：

（1）计算障碍点B到C之间的路径总数Kbc；

（2）计算A到障碍点B的路径总数Kab；

（3）计算无障碍点B时，A到C的路径总数Kac；

以上3个问题均可以由getPathNum函数计算，则实际结果应等于Kac-Kab*Kbc，也就是总路径数减去A经过B到C的路径数目，A经过B到C的路径等于A到B的路径总数乘以B到C的路径总数，程序如下：

int main()
{
	int x1 = 1, y1 = 1;
	int x2 = 2, y2 = 2;
	int x3 = 4, y3 = 4;
	int x = getPathNum( x3-x1, y3-y1 );
	int y = getPathNum( x3-x2, y3-y2 );
	int z = getPathNum( x2-x1, y2-y1 );
	cout<<x-y*z<<endl;
	return 0;
}

以上讨论均认为路径只能前进，不能后退（相对于目的地偏离）

写下这个博客的主要原因在于自己记录学习，必定存在疏漏，还望高手给出建议，谢谢！