AOJ 763.过河卒

184


题目



Description  


在一个n*m的矩阵上,A点有一个过河卒,需要走到目标B点。卒行走的规则:只能向下或者向右。每一步能水平或者垂直移动一个点(纵横线的交叉点)的距离。计算从A 点能够到达B点的路径的条数。
设行、列数为m和n, 2<=m,n<=20



Input  


只有一行,包含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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论