P1002-过河卒

P1002 [NOIP2002 普及组] 过河卒

解法

这一题目前了解到有两种解法，递归和动态规划(DP算法)。

递归

一开始我想到的方法是递归，通过递归罗列出卒走路的所有路线，再将成功的次数加起来。 但是这个问题上，用递归所要经历的分支实在是太多了，不出意外地超时了。 所以后续尝试将备忘录的思想和递归结合，设置一个二维数组当做备忘录，将走到一个点的路线数记录下来，这样以后再遇到需要这个点的路线数的情况，就不用再递归了，直去备忘录取数字就行。这样可以用空间换时间。最后证实是可行的。

#include <iostream>
#include <cmath>
#include <vector>
# define ll long long
// 递归函数，带备忘录
ll move(int x, int y, int a, int b, int c, int d, std::vector<std::vector<ll>>& memo) {
    // 如果当前位置与马的距离为 5，或超出了目标区域，或马挡住兵
    if (((x - c) * (x - c) + (y - d) * (y - d)) == 5 || x > a || y > b || (x == c && y == d)) {
        return 0;  // 这是错误的路线
    }
    
    // 如果到达目标点
    if (x == a && y == b) {
        return 1;  // 成功找到一条路线
    }

    // 检查备忘录，是否已经计算过这个点的结果
    if (memo[x][y] != -1) {
        return memo[x][y];  // 如果计算过，直接返回结果
    }

    // 计算从 (x, y) 到 (a, b) 的所有可能路线：向下走和向右走
    ll right = move(x, y + 1, a, b, c, d, memo);  // 向右走
    ll down = move(x + 1, y, a, b, c, d, memo);   // 向下走

    // 存储结果到备忘录中
    memo[x][y] = right + down;

    // 返回当前点的路径总数
    return memo[x][y];
}

int main() {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;

    // 创建备忘录，初始化为 -1，表示所有位置尚未计算
    std::vector<std::vector<ll>> memo(a + 1, std::vector<ll>(b + 1, -1));

    // 计算从 (0,0) 到 (a,b) 的路线总数
    ll result = move(0, 0, a, b, c, d, memo);

    // 输出结果
    std::cout << result << std::endl;

    return 0;
}

需要注意的是，存储路线数的变量一定要用long long类型，因为在第三个测试节点，路线数已经到了11位大小，超出了int和long(之前没考虑到这点，浪费了很多时间)。

DP算法

后面看了一下题目标签了解了一下DP算法，发现用dp确实简便了许多，递归还要套一层又一层，可能会栈溢出，DP算法只要一个双层循环就行了，方便了许多，以后遇到类似问题可以多一种思路。

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;

const int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
const int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
//马可以走到的位置

int bx, by, mx, my;
ll f[40][40];
bool s[40][40]; //判断这个点有没有马拦住
int main(){
    cin>>bx>>by>>mx>>my;
    bx += 1; by += 1; mx += 1; my += 1;
    //坐标+1以防越界
    f[1][0] = 1;//初始化
    s[mx][my] = 1;//标记马的位置
    for(int i = 1; i <= 8; i++) s[mx + fx[i]][my + fy[i]] = 1;
    for(int i = 1; i <= bx; i++){
        for(int j = 1; j <= by; j++){
            if(s[i][j]) continue; // 如果被马拦住就直接跳过
            f[i][j] = f[i - 1][j] + f[i][j - 1];
            //状态转移方程
        }
    }
    cout<<f[bx][by]<<endl;
    return 0;
}