动态规划解过河卒问题"/>
动态规划解过河卒问题
动态规划解过河卒问题
题目描述
棋盘上 A 点有一个过河卒,需要走到目标 B点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示,A点 (0, 0)、B点 (n, m),同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A点能够到达 B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
输入格式
一行四个正整数,分别表示 B点坐标和马的坐标。
输出格式
一个整数,表示所有的路径条数。
输入输出样例
输入 #1
6 6 3 3
输出 #1
6
说明/提示
对于 100% 的数据,1≤n,m≤20,0 ≤ 马的坐标≤20。
解题思路
我们首先以样例为例,看看路径有什么规律。
如上图所示,由于卒只能向右或向下移动,所以从A到B的路径就有如图的6条。
下面把所有点的路径条数整理如下:
从原点到点(i,j)的路径数f[i][j]=f[i-1][j]+f[i][j-1]
因为到达一个点(i,j),可能从点(i-1,j)或(i,j-1)到达,所以到(i,j)的路径数也就是到这两个点路径数之和。
可以确定转移方程就是f[i][j]=f[i-1][j]+f[i][j-1]
目标状态则为f[m][n]
完整代码
#include <iostream>
using namespace std;
const int ctrlx[9]={0,-2,-1,1,2,2,1,-1,-2};//以马为原点它所能控制到的点
const int ctrly[9]={0,1,2,2,1,-1,-2,-2,-1};
long long int f[25][25];
int mark[25][25];//标记被马控制的点
int main(){int m,n,horx,hory;cin>>m>>n>>horx>>hory; for(int i=0;i<9;i++){mark[ctrlx[i]+horx][ctrly[i]+hory]=1;} f[1][0]=1;for(int i=1;i<=m+1;i++){for(int j=1;j<=n+1;j++){if(mark[i-1][j-1]==1) f[i][j]=0;//如果是被标记的点,则为 0 else f[i][j]=f[i-1][j]+f[i][j-1];}}
// for(int i=0;i<=m+1;i++)
// {for(int j=0;j<=n+1;j++)
// cout<<f[i][j]<<" ";
// cout<<endl;
// }cout<<f[m+1][n+1];return 0;}
更多推荐
动态规划解过河卒问题
发布评论