#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
只要到达了边沿，就可以选择出还是不出。
这道题目用到了杨辉三角（帕斯卡三角），参考
打一张表，在表里边存放到距离（x，y）坐标能走的方案数，可以自己推一下，杨辉三角里边的数和所走产生的方案数一致。
然后利用用for循环遍历 n*m 这张图上所有边沿上的点到 （x，y）的所能走的方案数（通过一个函数实现找到具体点到（x， y）的方案数），并加起来。
| 2 | 1 | 2 | 3 | 4 |
| 1 | 1(x,y) | 1 | 1 | 1 |
| 2 | 1 | 2 | 3 | 4 |
| 3 | 1 | 3 | 6 | 10 |
| 4 | 1 | 4 | 10 | 20 |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = ;
LL dp[][];
LL Search(int x1, int y1, int x2, int y2) {
return dp[abs(x1 - x2) + abs(y1 - y2)][abs(x1 - x2)];
} int main() {
for(int i = ; i <= ; ++i) {
dp[i][] = ;
dp[i][] = i;
}
for(int i = ; i <= ; ++i) {
for(int j = ; j <= i; ++j) {
dp[i][j] = dp[i-][j-] + dp[i-][j];
dp[i][j] %= MOD;
}
}
int n, m, x, y;
LL ans;
while(scanf("%d %d %d %d", &n, &m, &x, &y) != EOF) {
ans = ;
if(n == || m == ) {
ans = n + m - ;
} else {
for(int i = ; i <= m; ++i) {
ans += Search(, i, x, y);
ans += Search(n, i, x, y);
}
for(int i = ; i < n; ++i) {
ans += Search(i, , x, y);
ans += Search(i, m, x, y);
}
}
ans %= MOD;
cout << ans << endl;
}
}