过河卒

P1002 过河卒 题目描述 棋盘上AAA点有一个过河卒,需要走到目标BBB点。卒行走的规则:可以向下、或者向右。同时在棋盘上CCC点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示,AAA点(0,0)(0, 0)(0,0)、BBB点(n,m)(n, m)(n,m)(nnn, mmm为不超过202020的整数),同样马的位置坐标是需要给出的。 现在要求你计算出卒从AAA点能够到达BBB点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。 输入输出格式 输入格式:

一行四个数据,分别表示BBB点坐标和马的坐标。 输出格式:

一个数据,表示所有的路径条数。 样例1: 6 6 3 3 输出1: 6 说明: 结果可能很大! 思路:数据范围可以longlong水过…,unsigned longlong当然也行… 一开始用dfs爆搜 标记马所能走到的位置,记为-1表示不能走,从起点深搜,向右向下超出边界或遇到马能到的点返回 只拿40分 40分代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans;
int n,m,c,d;
int a[500][500],dx[2]={0,1},dy[2]={1,0},dhorsex[10]={0,-1,-1,1,1,-2,-2,2,2},dhorsey[10]={0,-2,2,-2,2,1,-1,1,-1};
void dfs(int x,int y)
{
    if(x==n&&y==m)
    {
        ans++;
        return ;
    }
    if(x<0||y<0||a[x][y]==-1||x>n||y>m)return;
    else
    {
        for(int i=0;i<2;i++)
        {
            dfs(x+dx[i],y+dy[i]);
        }
    }
}
int main()
{
scanf("%d%d%d%d",&n,&m,&c,&d);
for(int i=0;i<=8;i++)
{
    if((c+dhorsex[i])>=0&&(d+dhorsey[i])>=0)
    {
        a[c+dhorsex[i]][d+dhorsey[i]]=-1;
    }
}
dfs(0,0);
cout<<ans<<endl;
    return 0;
}

最后看题解是记忆化递推,原来是入门dp题… 状态转移方程很好想:f[i][k]=f[i-1][k]+f[i][k-1](f[i][j]表示从(0,0)移动到(i,k)点一共可能的路径数目) 因为它只能来自上一状态(两种选择,往下走,往右走) ACcode

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans;
int n,m,c,d;
ll a[500][500];
int dhorsex[10]={0,-1,-1,1,1,-2,-2,2,2},dhorsey[10]={0,-2,2,-2,2,1,-1,1,-1},flag[500][500];
int main()
{
scanf("%d%d%d%d",&n,&m,&c,&d);
for(int i=0;i<=8;i++)
{
    if((c+dhorsex[i])>=0&&(d+dhorsey[i])>=0)
    {
        flag[c+dhorsex[i]][d+dhorsey[i]]=-1;
    }
}
a[1][0]=1;
for(int i=1;i<=n+1;i++)
{
    for(int j=1;j<=m+1;j++)
    {
        a[i][j]=a[i-1][j]+a[i][j-1];
      //  printf("%d\n",a[i][j]);
            if(flag[i-1][j-1]==-1)a[i][j]=0;
    }
}
cout<<a[n+1][m+1]<<endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序算法之我观

    笔者今年是xmu大一新生 9月初学编程 学到泡排的时候就对排序这一块深入了解 (也只是很粗浅地学习了一下) 写这篇文章的初衷就是复习一下之前所学,有不足...

    glm233
  • Python Tips(1) 数字与字符串之间转换,采用内置函数

    glm233
  • 八皇后递归实现

    八皇后问题,是指在8X8d的棋盘上放置八个皇后,使得她们不能互相攻击,皇后的攻击范围是同行同列,或是在一条对角线上,满足...

    glm233
  • HDOJ(HDU) 2504 又见GCD(利用最大公约数反推)

    谙忆
  • 剑指OFFER之重建二叉树(九度OJ1385)

    题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

    用户1154259
  • 力扣(LeetCode)刷题,简单+中等题(第29期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • 2019 CCPC 重现赛 1006 基环树

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2965768
  • 挑战程序竞赛系列(30):3.4矩阵的幂

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • C语言函数求参数顺序问题

    对于函数func,先求右边x+=2参数,返回x=8,然后计算结果。也就是传递给形参的两个值都是8,返回值为16。

    用户6755376
  • cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)

    答案=任意一种方案 - 至少有\(1\)位为\(1\)的方案 + 至少有两位为\(1\)的方案 - 至少有三位为\(1\)的方案

    attack

扫码关注云+社区

领取腾讯云代金券