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

时间:2023-12-05 10:52:44

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;
}