洛谷P1002过河卒求解

Question

原题 洛谷P1002 [NOIP2002 普及组] 过河卒
我用的c++写的，但我输入6 6 3 3时它却输出10,而不是6
我的思路是首先数学上就是标数法呗，编程上也就dp动规，但为啥它会错呀？
我的代码:

#include<iostream>

using namespace std;

bool g[1001][1001];
long long dp[1001][1001]; // 使用 long long 类型以避免整数溢出

int main(){
    int n, m;
    int x, y;
    cin >> n >> m >> x >> y;
    g[x-2][y-1] = 1;
    g[x-1][y-2] = 1;
    g[x+1][y-2] = 1;
    g[x+2][y-1] = 1;
    g[x+2][y+1] = 1;
    g[x+1][y+2] = 1;
    g[x-1][y+2] = 1;
    g[x-2][y+1] = 1;
    
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            if(i == 0 || j == 0){
                dp[i][j] = 1;
            }
            else if(g[i][j]){
                dp[i][j] = 0;
            }
            else{
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    
    cout << dp[n][m];
    
    return 0;
}

注:编译器版本MinGW-w64 GCC 11.4.0 64-bit Debug

Answer 1

引自免费微信小程序：皆我百晓生

在分析您的代码前，让我们先确认一下题目描述。洛谷P1002题目的大致意思是：在一个n*m的棋盘上，从起点(1, 1)出发的一个过河卒，每次可以向上、下、左、右或对角线方向移动一步，但不能移出棋盘边界，并且已经走过的位置不能再走（即棋盘格子标记为障碍）。现在要求计算从起点出发，能够到达的不同位置的数量。

问题在于，您初始化棋盘状态时似乎只设置了起点周围的8个格子为障碍，并没有将起点自身也设置为已访问。根据题目规则，起点也应该视为不可再行进的位置。

以下是修改后的代码：

#include<iostream>

using namespace std;

bool g[1001][1001];
long long dp[1001][1001]; // 使用 long long 类型以避免整数溢出

int main(){
    int n, m;
    int x = 1, y = 1; // 假设起点坐标是 (1, 1)
    cin >> n >> m;
    
    // 将起点和其周围八个格子设置为障碍
    g[x-1][y-1] = 1;
    g[x][y-2] = 1;
    g[x+1][y-1] = 1;
    g[x+2][y] = 1;
    g[x+1][y+1] = 1;
    g[x][y+2] = 1;
    g[x-1][y+1] = 1;
    g[x-2][y] = 1;

    // 初始化dp数组，边界条件
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            if(i == 0 || j == 0){
                dp[i][j] = 1; // 边界位置可到达计数为1
            }
            else if(g[i][j]){
                dp[i][j] = 0; // 障碍位置不可到达计数为0
            }
            else{
                dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 根据动态规划递推公式计算
            }
        }
    }

    cout << dp[n][m] << endl; // 输出能到达的不同位置数量
    
    return 0;
}

请尝试使用上述修改后的代码重新编译并运行。同时，请确保输入样例中的 x 和 y 不需要额外输入，因为题目默认起点就是 (1, 1)。如果还有其他问题，请提供详细的测试用例和预期输出，以便进一步排查错误。