题目描述
棋盘上 A A A 点有一个过河卒,需要走到目标 B B B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C C C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示,A A A 点 ( 0 , 0 ) (0, 0) ( 0 , 0 ) 、B B B 点 ( n , m ) (n, m) ( n , m ) ,同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A A A 点能够到达 B B B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
输入格式
一行四个正整数,分别表示 B B B 点坐标和马的坐标。
输出格式
一个整数,表示所有的路径条数。
输入输出样例
输入 #1
6 6 3 3
输出 #1
6
说明/提示
对于 100 % 100 \% 100% 的数据,1 ≤ n , m ≤ 20 1 \le n, m \le 20 1 ≤ n , m ≤ 20 ,0 ≤ 马的坐标 ≤ 20 0≤ 马的坐标 \le 20 0 ≤ 马的坐标 ≤ 20 。
分析
设 d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] 为从 ( 0 , 0 ) (0,0) ( 0 , 0 ) 走到点 ( i , j ) (i,j) ( i , j ) 的路径数。对于没有任何状态的格点图,显然有状态转移方程 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][j]=dp[i-1][j]+dp[i][j-1] d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] ;然而在题给的图中,有一些点是不可走的,对于一个被马控制的点 ( i , j ) (i,j) ( i , j ) 有 d p [ i ] [ j ] = 0 dp[i][j]=0 d p [ i ] [ j ] = 0 。综上所述,需要预处理出马可以控制的 9 9 9 个点,定义 i s [ i ] [ j ] is[i][j] i s [ i ] [ j ] ,若 ( i , j ) (i,j) ( i , j ) 被马控制,i s [ i ] [ j ] is[i][j] i s [ i ] [ j ] 为真。
有状态转移方程
$$
dp[i][j]=\begin{cases}0&,is[i][j]=1\\dp[i-1][j]+dp[i][j-1]&,is[i][j]=0
\end{cases}
$$
接下来分析边界条件,即确定 d p [ i ] [ 0 ] ( 1 ≤ i ≤ n ) dp[i][0](1\le i\le n) d p [ i ] [ 0 ] ( 1 ≤ i ≤ n ) 和 d p [ 0 ] [ j ] ( 1 ≤ j ≤ m ) dp[0][j](1\le j\le m) d p [ 0 ] [ j ] ( 1 ≤ j ≤ m ) 。由于过河卒只能向下和向右走,因此对于边界上某一点,走到这个点上的路径数至多为 1 1 1 ;若沿着边界一直走,碰到一个被马控制的点,那么边界上剩下的点都不可达,路径数为 0 0 0 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include <iostream> #define N 30 using namespace std;long long dp[N][N];int n,m;int x,y;bool is[N][N];int main () { cin>>n>>m>>x>>y; int i,j; is[x][y]=1 ; if (x>=2 &&y>=1 ) is[x-2 ][y-1 ]=1 ; if (x+2 <=n&&y>=1 ) is[x+2 ][y-1 ]=1 ; if (x>=2 &&y+1 <=m) is[x-2 ][y+1 ]=1 ; if (x+2 <=n&&y+1 <=m) is[x+2 ][y+1 ]=1 ; if (x>=1 &&y>=2 ) is[x-1 ][y-2 ]=1 ; if (x+1 <=n&&y>=2 ) is[x+1 ][y-2 ]=1 ; if (x>=1 &&y+2 <=m) is[x-1 ][y+2 ]=1 ; if (x+1 <=n&&y+2 <=m) is[x+1 ][y+2 ]=1 ; bool ok=1 ; for (i=1 ;i<=n;i++) { if (is[i][0 ]) ok=0 ; if (ok) dp[i][0 ]=1 ; else dp[i][0 ]=0 ; } ok=1 ; for (j=1 ;j<=m;j++) { if (is[0 ][j]) ok=0 ; if (ok) dp[0 ][j]=1 ; else dp[0 ][j]=0 ; } for (i=1 ;i<=n;i++) { for (j=1 ;j<=m;j++) { if (is[i][j]) dp[i][j]=0 ; else dp[i][j]=dp[i-1 ][j]+dp[i][j-1 ]; } } cout<<dp[n][m]<<endl; return 0 ; }