wikioi 1010 过河卒


/*
转移方程为dp[i][j]=dp[i-1][j]+dp[i][j-1]
表示到(i,j)这个格子所需要的最多的步数
注意几个特殊的地方
马所在的地方,以及i=0;j=0的时候
*/
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> typedef long long ll; using namespace std; int dp[200][200]; int main() { int x,y,n,m; cin>>n>>m>>x>>y; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j]=1; dp[x][y]=0; dp[x+1][y+2]=0; dp[x+2][y+1]=0; if(x-1>=0)dp[x-1][y+2]=0; if(x-2>=0)dp[x-2][y+1]=0; if(x-1>=0&&y-2>=0)dp[x-1][y-2]=0; if(x-2>=0&&y-1>=0)dp[x-2][y-1]=0; if(y-1>=0)dp[x+2][y-1]=0; if(y-2>=0)dp[x+1][y-2]=0; for(int i=0;i<=n;i++) { for(int j=0;j<=m;j++) { if(!dp[i][j]) continue; if(i==0&&j==0) continue; if(i==0)dp[i][j]=dp[i][j-1]; else if(j==0)dp[i][j]=dp[i-1][j]; else dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } cout<<dp[n][m]<<endl; return 0; }

优质内容筛选与推荐>>
1、HTTP协议浅谈
2、javascript:滚动新闻
3、ROSE
4、枚举算法总结 coming~^.*
5、dcef for delphi


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号