hihocoder 1191 小W与网格 (组合数)

描述

给定一个n*m的网格，左上角(1, 1)，右下角(n, m)。

小w在(i, j)，他会从"上左下右"四个方向中选定两个不同但正交的方向，然后他只能沿着这两个方向走，直到他走出网格。

小w想知道有多少种不同的走法。

两个走法不同当且仅当所经过的格子的集合不同。

输入

输入包含多组数据。

每组数据一行四个整数n, m, i, j。(1 <= i <= n <= 100, 1 <= j <= m <= 100)

输出

对于每组数据，输出一个整数表示方案数，答案对1000000007取模。

样例解释

无论怎么走，要么覆盖一格，要么覆盖两格。

样例输入

2 1 1 1

样例输出

2

题目链接：http://hihocoder.com/problemset/problem/1191

题目分析：又是这种方格里面走路方案数的问题，任意两格(x1, y1) ，(x2, y2)间走路的方案数为c[abs(x1 - x2)][abs(x1 - x2) + abs(y1 - y2)]，c是组合数，那么对于这题，我要求的就是(i,j)这个点到四边的方案数和，枚举一下边界用上面的公式算就可以了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 205;
int const MOD = 1e9 + 7;
int c[MAX][MAX];

void pre()
{
    c[0][0] = 1;
    for(int i = 1; i <= 200; i++)
    {
        c[i][0] = 1;
        for(int j = 1; j <= 200; j++)
            c[i][j] = (c[i - 1][j] % MOD + c[i - 1][j - 1] % MOD) % MOD;
    }
}

int main()
{
    int n, m, i, j;
    pre();
    while(scanf("%d %d %d %d", &n, &m, &i, &j) != EOF)
    {
        int ans = 0;
        for(int x = 1; x <= n; x++)
        {
            for(int y = 1; y <= m; y++)
            {
                if(x == 1 || x == n || y == 1 || y == m)
                {
                    int xx = abs(x - i);
                    int yy = abs(y - j);
                    ans = (ans % MOD + c[xx + yy][xx] % MOD) % MOD;
                }
            }
        }
        printf("%d\n", ans);
    }
}

版权声明：本文为博主原创文章，未经博主允许不得转载。