洛谷P1002 过河卒 [2017年4月计划 动态规划15]

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;

}