P1002 过河卒

蔚落 2022-06-07 13:58 224阅读 0赞

[过河卒][Link 1]

首先初始化地图，去掉不能走的点；  
由于卒的走的方向只有向右或向下一步，因此对于点(x,y)，到达该点的路径数为f\[x\]\[y\] = f\[x-1\]\[y\] + f\[x\]\[y-1\]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    
    long long map[22][22];
    void init(int x,int y){
        if (x>=0&&y>=0) map[x][y] = -1;
    }
    
    int main(){
        memset(map,0,sizeof(map));
    
        int a,b;
        scanf("%d%d",&a,&b);
        int ha,hb;
        scanf("%d%d",&ha,&hb);
        init(ha,hb);
        init(ha+2,hb+1);init(ha+2,hb-1);init(ha+1,hb+2);init(ha+1,hb-2);
        init(ha-2,hb+1);init(ha-2,hb-1);init(ha-1,hb+2);init(ha-1,hb-2);
        map[0][0] = 1;
        for (int i = 0;i <= a;i++){
            for (int j = 0;j <= b; j++){
                if (i == 0&&j==0) continue;
                if (map[i][j] == -1){
                    map[i][j] = 0;
                }else{
                    if (i-1<0)  map[i][j] = map[i][j-1];
                    else if (j-1<0) map[i][j] = map[i-1][j];
                    else map[i][j] = map[i-1][j] + map[i][j-1];
                }
        // std::cout<<map[i][j]<<" ";
            }    
        //std::cout<<std::endl;
        }
        std::cout<<map[a][b];
        return 0;
    }

[Link 1]: https://www.luogu.org/problem/show?pid=1002

发表评论取消回复

表情：

评论列表（有 0 条评论，224人围观）

还没有评论，来说两句吧...

相关阅读

相关 P1002 过河卒--洛谷--经典DP

题目描述棋盘上 A点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方

柔光的暖阳◎/ 2023年07月13日 04:27/ 0 赞/ 21 阅读

相关洛谷1002 过河卒

题目描述棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点

蔚落/ 2023年07月06日 14:44/ 0 赞/ 27 阅读

相关 P1002 过河卒(洛谷）

题目描述棋盘上 A 点有一个过河卒，需要走到目标B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方

比眉伴天荒/ 2023年05月22日 02:29/ 0 赞/ 16 阅读

相关过河卒（动态规划）

Problem E: 过河卒 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 7 Solved: 2 \[

Bertha 。/ 2022年07月31日 15:18/ 0 赞/ 179 阅读

相关马拦过河卒

Problem Description 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步

太过爱你忘了你带给我的痛/ 2022年07月13日 03:40/ 0 赞/ 156 阅读

相关马拦过河卒

马拦过河卒描述 Description 　　棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和

- 日理万妓/ 2022年07月11日 08:51/ 0 赞/ 180 阅读

相关 1010 过河卒 (dfs)

题目描述 Description 　如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所

今天药忘吃喽~/ 2022年06月18日 09:44/ 0 赞/ 186 阅读

相关 P1002 过河卒

[过河卒][Link 1] 首先初始化地图，去掉不能走的点；由于卒的走的方向只有向右或向下一步，因此对于点(x,y)，到达该点的路径数为f\[x\]\[y\] = f\

蔚落/ 2022年06月07日 13:58/ 0 赞/ 225 阅读

相关马拦过河卒

1.知识点：递推 2.题意：棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称

短命女/ 2022年05月30日 08:49/ 0 赞/ 179 阅读

相关 P1002 过河卒（DP入门题）

题目链接：[https://www.luogu.org/problemnew/show/P1002][https_www.luogu.org_problemnew_show_P

短命女/ 2022年03月15日 04:34/ 0 赞/ 214 阅读