洛谷题解 P1002 【过河卒】

题目

题目描述

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A 点 (0,0) 、B 点 (n,m) ，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 B 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

输入输出样例

输入

6 6 3 3

输出

6

说明/提示

对于100%的数据，1≤n,m≤20，0≤马的坐标≤20。

解题思路

一道dp，即动态规划，又名动规题，
dp题目最主要是找出状态转移方程，
这道题可以根据样例模拟一下 , 就可以求出状态转移方程了。

步骤大概是这样的：
以A表示A点 , B是B点, M是马的位置, X是被马拦着不能走的点。(别告诉我你们连马走"日"字都不知道)

 A 0 0 0 0 0 00 0 X 0 X 0 00 X 0 0 0 X 00 0 0 M 0 0 00 X 0 0 0 X 00 0 X 0 X 0 00 0 0 0 0 0 B

其中每个点的值代表的是当前这个点会有几条路径用过这个点。(路径指的是从A到B的路径)

 1 1 1 1 1 1 11 2 X 1 X 1 21 X 0 1 1 X 21 1 1 M 1 1 31 X 1 1 0 X 31 1 X 1 X 0 31 2 2 3 3 3 6

这样很容易能看出来，
f[i][j]这个点 , 从(0,0)位置到B点 , 会经过他这个点的路线有：

f[1][1] = 1
f[i][j] = f[i-1][j] + f[i][j-1]

但是这个方程是推不出结果的 , 因为这样 A 点会在一开始的时候被覆盖成0！
所以修改以后的方程就是

f[1][1] = 1
f[i][j] = max (f[i-1][j] + f[i][j-1] , f[i][j])

当然还有不用max函数的转移方程

f[1][0] = 1
f[i][j] = f[i-1][j] + f[i][j-1]

f[1][1]这个点通过从f[1][0]这个点直接转移过来，
因为转移方程的时候需要 i-1 和 j-1，
而初始化被马挡住的位置的时候会有 i-2, j-2 ,
所以如果不从 2 开始就会因数组越界而 WA 一个点
从 2 开始就是把每个点的坐标都加了 2 而已

另外题目说明写着

结果可能很大！

但是 unsigned long long 就可以过去

代码

#include<bits/stdc++.h>//万能头文件
using namespace std;
const int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
const int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
//马可以走到的位置
int bx,by,mx,my;
unsigned long long f[30][30];//f[i][j]代表从A点到(i,j)会经过的线路数
bool s[25][25];//判断这个点有没有被马盯着
int main()
{cin >> bx >> by >> mx >> my;bx += 2; by += 2; mx += 2; my += 2;//以防越界f[2][2] = 1;//初始化s[mx][my] = 1;//标记马的位置for (int i = 1; i <= 8; i++)s[mx + fx[i]][my + fy[i]] = true;//这个点被马盯着for (int i = 2; i <= bx; i++)for (int j = 2; j <= by; j++){if(s[i][j])continue;//如果这个点被马盯着，卒就不过去f[i][j] = max(f[i][j] , f[i - 1][j] + f[i][j - 1]); //状态转移方程}cout << f[bx][by] << endl ;return 0;
}