问题描述

在一个m行n列的网格中，每个网格的各边的长度均相等，求由A(x1,y1)点到达B(x2,y2)点的最短路径条数，其中1<=m,n<=30。输入保证x2>=x1,y2>=y1 如有下图网格，起点和终点分别是A(1,1),B（2，3） 则最短路线是:

(1,1)->(1,2)->(1,3)->(2,3)
(1,1)->(2,1)->(2,2)->(2,3)
(1,1(->(1,2)->(2,2)->(2,3)

共3条最短路线

输入格式

第一行输入网格的行数m和列数n 第二行输入A点的坐标 第三行输入B点的坐标

输出格式

输出一个整数,表示从A点到达B点的最短路线条数

输入样例

6 7
1 1
2 3

输出样例

3

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 40;

int n, m;
int x1, y1, x2, y2;
int f[N][N];

int main() {
	cin >> m >> n >> x1 >> y1 >> x2 >> y2;
	if (x1 >= x2) swap(x1, x2);
	if (y1 >= y2) swap(y1, y2);
	
	memset(f, 0, sizeof f);
	
	for (int i = x1; i <= n; i ++ ) 
		for (int j = y1; j <= m; j ++ ) {
			if (i == x1 || j == y1) f[i][j] = 1;
			else f[i][j] = f[i - 1][j] + f[i][j - 1];
		}
	
	cout << f[x2][y2];
	
	return 0;
	
}