[已解决]过河卒问题

柿子饼同学

#include <bits/stdc++.h>
using namespace std;

int bx, by, hx, hy;
int hxd[] = {2, 1, -1, -2, -2, -1, 1, 2};
int hyd[] = {1, 2, 2, 1, -1, -2, -2, -1};
long long dp[24][24] = {0};
int arr[24][24] = {0};
int main(){
    scanf("%d%d%d%d", &bx, &by, &hx, &hy);
    bx += 3; by += 3; //加一行一列用来存第0行第0列 , 加两行用来让马的控制点不出界
    arr[hx][hy] = 1;
    
    for(int i = 0; i < bx; i++){
        dp[i][0] = 1;
    }
    for(int i = 1; i < by; i++){
        dp[0][i] = 1;
    }                                       //上面两个循环就是把第 0 行第 0 列的方法弄成1
    for(int i = 0; i < 8; i++){
        arr[hx + hxd[i]][hy + hyd[i]] = 1;
        dp[hx + hxd[i]][hy + hyd[i]] = 0;
    }//马的控制点在 arr 中显示 , 并且把第 0 行 0 列的控制点方法变成 0

    for(int i = 1; i <= bx-3; i++){
        for(int j = 1; j <= by-3; j++){
            if(arr[i][j]){
                continue;   //如果碰到马的控制点就不管
            }
            else{
                dp[i][j] = dp[i-1][j] + dp[i][j-1]; 
            }
        }
    }//状态转移

    printf("%d", dp[bx-3][by-3]);
    return 0;
}

题目如上 , 其中 , 状态转移方程是 dp(i, j) = dp(i-1, j) + dp(i, j-1)
dp(i, j) 是到点 (i, j) 的方法数
题目的链接 : https://www.luogu.com.cn/problem/P1002
我的代码能做出来 , 但是只能做一点点 , 有两个测试点超时 , 一个错误 , 两个正确
不知道为什么 , 或者有没有什么优化方法
求问 , 谢谢

最佳答案

月排行榜 / 总排行榜

jhq999

2022-3-28 17:35:53

有公式，看答案吧

跳转到最佳答案楼层

jhq999

有公式，看答案吧

傻眼貓咪

我的代码不通过吗？那好吧

柿子饼同学

jhq999 发表于 2022-3-28 17:35
有公式，看答案吧

柿子饼同学

傻眼貓咪 发表于 2022-3-28 17:57
我的代码不通过吗？那好吧

不不不 , 我毕竟还在学习 , 只是想先自己做一下
最近网课时间太少了...

傻眼貓咪

柿子饼同学 发表于 2022-3-28 18:24
不不不 , 我毕竟还在学习 , 只是想先自己做一下
最近网课时间太少了...

我以为我的代码有错
慢慢来吧，可以如 2楼大佬说的那样，参考答案吧。

柿子饼同学

傻眼貓咪 发表于 2022-3-28 19:30
我以为我的代码有错
慢慢来吧，可以如 2楼大佬说的那样，参考答案吧。

好嘞 , 现在我在考语文

柿子饼同学

傻眼貓咪 发表于 2022-3-28 19:30
我以为我的代码有错
慢慢来吧，可以如 2楼大佬说的那样，参考答案吧。

哈哈哈今天自己写了代码 , 全过了 , 比之前写的简单

傻眼貓咪

柿子饼同学 发表于 2022-3-31 22:44
哈哈哈今天自己写了代码 , 全过了 , 比之前写的简单