P1002 过河卒
题目描述
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过20的整数)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入输出格式
输入格式：
一行四个数据，分别表示B点坐标和马的坐标。
输出格式：
一个数据，表示所有的路径条数。
输入输出样例
输入样例#1：
6 6 3 3
输出样例#1：
6
说明
结果可能很大！
很久以前做过的一个题，那时候60分，现在才知道因为没开longlong。。
比（非）较（常）水就不多说了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define swap(a,b) ((a)^=(b)^=(a)^=(b))
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))
int read()
{
int x = 0;char ch = getchar();char c = ch;
while(ch > '9' || ch < '0')c = ch,ch = getchar();
while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0',ch = getchar();
if(c == '-')return -x;
return x;
}
const int MOD = 1000007;
const int INF = 0x3f3f3f3f;
const int MAXN = 100 + 10;
const int MAXM = 100 + 10; int dir[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}}; long long dp[1000][1000];
bool b[1000][1000];
int tmp1;int tmp2;
int x,y; int main()
{
tmp1 = read();tmp2 = read();
x = read();y = read();
for(int i = 0;i < 8;i ++)
{
if(x + dir[i][0] >= 0 && y + dir[i][1] >= 0)
b[x + dir[i][0]][y + dir[i][1]] = true;
}
b[x][y] = true;
if(!b[0][1])
dp[0][1] = 1;
if(!b[1][0])
dp[1][0] = 1;
for(int i = 0;i <= tmp1;i ++)
{
for(int j = 0;j <= tmp2;j ++)
{
if(b[i][j])
{
dp[i][j] = 0;
continue;
}
if(j >= 1)
dp[i][j] += dp[i][j - 1];
if(i >= 1)
dp[i][j] += dp[i - 1][j];
}
}
printf("%lld", dp[tmp1][tmp2]);
return 0;
}