题目
Description
在一个n*m的矩阵上,A点有一个过河卒,需要走到目标B点。卒行走的规则:只能向下或者向右。每一步能水平或者垂直移动一个点(纵横线的交叉点)的距离。计算从A 点能够到达B点的路径的条数。
设行、列数为m和n, 2<=m,n<=20Input
只有一行,包含4个整数,即B点坐标(x1,y1) 和 A点坐标(x2,y2),
保证A,B在地图内。Output
一个整数,为路径的条数,答案对1000000007取模
Sample Input
6 6 3 2
Sample Output
35
Hint
可能走不到
题解
递推(dp)或者组合数
最后答案记得取模
代码
/* By:OhYee Github:OhYee HomePage:http://www.oyohyee.com Email:oyohyee@oyohyee.com Blog:http://www.cnblogs.com/ohyee/ かしこいかわいい? エリーチカ! 要写出来Хорошо的代码哦~ */ #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <vector> #include <list> #include <queue> #include <stack> #include <map> using namespace std; //DEBUG MODE #define debug 0 //循环 #define REP(n) for(int o=0;o<n;o++) //初始化 #define mst(a,n) memset(a,n,sizeof(a)) int Map[25][25]; const int MOD = 1000000007; bool Do() { int x1,y1,x2,y2; if(scanf("%d%d%d%d",&x1,&y1,&x2,&y2) == EOF) return false; mst(Map,0); Map[x2][y2] = 1; for(int i = x2;i <= x1;i++) for(int j = y2;j <= y1;j++) if(!(i == x2&&j == y2)) Map[i][j] = (Map[i][j - 1] + Map[i - 1][j]) % MOD; printf("%d\n",Map[x1][y1]); return true; } int main() { while(Do()); return 0; }