听说水区大佬多

一道站外题用c++解决下面的问题题目描述小T是一个有梦想的小兵。众所周知，在国际象棋的规则中，小兵走到对面底线后，可以升变为皇后、车等强力棋子，但不能不变。不过小T并不是一个普通的小兵，他理解不了斜吃、吃过路兵等国际象棋的规则，因此他只打算向右或者向下走，并且每次只能移动一个格子。另外，由于某些格子有友方棋子，因此这些格子是不能走的。小T想知道从他现在的位置出发，有几种不同的路线可以升变。

当且仅当两条路线长度一致、路线经过的点集相同、经过这些点的顺序相同，我们才认为这是相同的路线，否则均是不同的路线。

输入格式第一行一个整数n,m，代表棋盘是n*n的，并且此时还有m个友方棋子（不含小T）。

第二行两个整数x,y，代表小T的位置。

后续m行，每行两个整数ai,bi，代表友方棋子的位置。

棋盘左上角的位置为1,1，右下角的位置为n,n。

输出格式输出一个整数，代表升变路线的个数。

样例数据样例输入#1 3 1 1 1 2 2 样例输出#1 2 样例解释：小T初始位于(1,1)，(2,2)格不能走。

可以连续向下走两格升变，或者向右走两格再向下走两格升变。

数据范围 2<=n<=20,0<=m<=5 1<=x,y,ai,bi<=n 保证小T开始不会处于底线，不会有两个棋子在一个位置（小T也算棋子）。

CPP

#include <iostream>
#include <vector>
using namespace std;

int n, m;
int xt, yt; // 小T的位置
vector<pair<int, int> > obstacles; // 友方棋子位置
vector<vector<int> > dp; // 用于存储中间结果的动态规划数组

int dfs(int x, int y) {
    // 边界情况处理
    if (x == n && y == n) {
        return 1; // 到达底线，返回一种路线
    }
    if (x > n || y > n) {
        return 0; // 越界，返回0种路线
    }
    for (int i = 0; i < obstacles.size(); ++i) {
        if (x == obstacles[i].first && y == obstacles[i].second) {
            return 0; // 遇到友方棋子，返回0种路线
        }
    }
    // 如果之前已经计算过当前位置的结果，则直接返回
    if (dp[x][y] != -1) {
        return dp[x][y];
    }
    // 继续向右和向下搜索，并将结果保存在dp中
    dp[x][y] = dfs(x + 1, y) + dfs(x, y + 1);
    return dp[x][y];
}

int main() {
    cin >> n >> m;
    cin >> xt >> yt;
    dp = vector<vector<int> >(n + 1, vector<int>(n + 1, -1)); // 初始化dp数组为-1
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        obstacles.push_back(make_pair(a, b));
    }
    int result = dfs(xt, yt);
    cout << result << endl;
    return 0;
}

错了一个点

讨论操作

回复

相关推荐

听说水区大佬多