首页 > 代码库 > 过河卒

过河卒

链接

分析:当前点的情况仅由其左边和上边的点决定,然后马会走过的点标记一下即可

技术分享
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "string"
 5 using namespace std;
 6 const int maxn=30;
 7 int vis[maxn][maxn];
 8 long long dp[maxn][maxn];
 9 int n,m,x,y;
10 int main()
11 {
12     cin>>n>>m>>x>>y;
13     vis[x][y]=1;
14     vis[x+2][y+1]=1;
15     vis[x+1][y+2]=1;
16     vis[x-1][y+2]=1;
17     vis[x-2][y+1]=1;
18     vis[x-2][y-1]=1;
19     vis[x-1][y-2]=1;
20     vis[x+1][y-2]=1;
21     vis[x+2][y-1]=1;
22     dp[1][0]=1;
23     for(int i=1;i<=n+1;i++){
24         for(int j=1;j<=m+1;j++){
25             dp[i][j]=dp[i-1][j]+dp[i][j-1];
26             if(vis[i-1][j-1])
27                 dp[i][j]=0;
28         }
29     }
30     cout<<dp[n+1][m+1]<<endl;
31 }
View Code

 

过河卒