洛谷题单指南-递推与递归-P1002 [NOIP2002 普及组] 过河卒

原题链接：https://www.luogu.com.cn/problem/P1002

题意解读：从A（0,0）点走到B（n，m）点，只能向右或者向下，C点以及其控制点不能走。

解题思路：

根据题意，此题要么递归（DFS），要么递推（动态规划）

先分析数据规模，最大从起点到终点要走40步，每个步有2种走法，一共2⁴⁰种路径，DFS会超时，且方案数必须用long long

采用递推更合适，

设dp[i][j]是从(0, 0)到(i, j)的路径数，而(i, j)只能从(i - 1, j)或者(i, j - 1)走过去，

因此：

如果(i, j)不是马的控制点，有dp[i][j] = dp[i-1][j] + dp[i][j-1]

如果(i, j)是马的控制点，有dp[i][j] = 0

初始时：dp[0][0] = 1，从自己到自己只有一种方案

100分代码：

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

const int N = 25;

int n, m, x, y;

bool vis[N][N]; //马的控制点
int dx[8] = {2, 1, -1, -2, -2, -1, 1,  2 };
int dy[8] = {1, 2, 2,  1,  -1, -2, -2, -1};

long long dp[N][N]; //dp[i][j]表示从(0,0)到(i，j)的路径条数

void init()
{
    vis[x][y] = true;
    for(int i = 0; i < 8; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx <= n && ny >= 0 && ny <= m)
        {
            vis[nx][ny] = true;
        }
    }
}

int main()
{
    cin >> n >> m >> x >> y;

    init();

    dp[0][0] = 1;

    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            if(vis[i][j]) continue; //如果是马的控制点，则dp[i][j] = 0
            if(i - 1 >= 0) dp[i][j] += dp[i - 1][j];
            if(j - 1 >= 0) dp[i][j] += dp[i][j - 1];
        }
    }

    cout << dp[n][m];

    return 0;
}