牛客算法入门DP：过河卒

本文主要是介绍牛客算法入门DP：过河卒，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0x00 题目来源

过河卒
经典!

0x10 Tag

线性dp

0x20 题目描述

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A 点 (0, 0) B 点 (n, m)，同样马的位置坐标是需要给出的。
棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A 点 (0, 0)、B 点 (n, m)，同样马的位置坐标是需要给出的。

0x30 思路与算法

大一室友教我的第一道动态规划题（但他妹讲明白。
由于卒子只能向下或者向右移动，那么该点 $(i, j)$ 只能由 $(i - 1, j)$ 或者 $(i, j - 1)$ 的卒子移动而来；动态规划的转移方程就显而易见了。 $f (i, j) = f (i - 1, j) + f (i, j - 1)$

$f (i, j)$ 存储着该点的方案数。

但是，🐎的存在让我们必须考虑限制条件，如果该点的左边点或者上边点被马控制，那么显然卒子不可能在此点经过，我们需要舍弃该方案数。

最后输出 $f (x, y)$ 的方案即可。

0x31 代码实现

声明

ll dp[25][25];
bool vis[25][25];
int x,y,x_0,y_0;
int dx[8]={2,1,-1,-2,-2,-1,1,2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};

vis数组记录是否被马控制；x，y为终点；x_0,y_0为马的坐标；
初始化

vis[x_0][y_0]=1;for(int i=0;i<8;++i){vis[x_0+dx[i]][y_0+dy[i]]=1;}//initdp[0][0]=1;

记录被控制点坐标，dp[0][0]表示最初的原点方案数为1；
实现细节

	ll ans=0;	if(check(i,j-1)&&!vis[i][j-1]) ans+=dp[i][j-1];if(check(i-1,j)&&!vis[i-1][j]) ans+=dp[i-1][j];dp[i][j]=ans;

在不越界且不受限制的情况下，方案数可以加和；

0x32 完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define HACK freopen("test.in", "r", stdin);freopen("test.out", "w", stdout);
// #define LOCAL_JUDGEll dp[25][25];
bool vis[25][25];
int x,y,x_0,y_0;
int dx[8]={2,1,-1,-2,-2,-1,1,2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
bool check(int a,int b)
{return a>=0&&a<=x&&b>=0&&b<=y;
}
int main()
{#ifdef LOCAL_JUDGEHACK;#endifcin>>x>>y>>x_0>>y_0;vis[x_0][y_0]=1;for(int i=0;i<8;++i){vis[x_0+dx[i]][y_0+dy[i]]=1;}//initdp[0][0]=1;for(int i=0;i<=x;++i)for(int j=0;j<=y;++j){if(i==0&&j==0) continue;if(vis[i][j]==1) continue;ll ans=0;if(check(i,j-1)&&!vis[i][j-1]) ans+=dp[i][j-1];if(check(i-1,j)&&!vis[i-1][j]) ans+=dp[i-1][j];dp[i][j]=ans;}// dpcout<<dp[x][y];return 0;
}