2

我有一个奇怪的问题。我在 C++ 中有以下代码：

int grid[h][w]; int dp[h][w]; int p[h][w];

for(int y = 0; y < h; y++)
    for(int x = 0; x < w; x++)
        cin >> grid[y][x];

// base case
for(int y = 0; y < h; y++) dp[y][0] = grid[y][0];


// fill rest
for(int x = 1; x < w; x++)
{
    for(int y = 0; y < h; y++)
    {
        dp[y][x] = min(dp[y][x-1], min(dp[(y-1)%h][x-1], dp[(y+1)%h][x-1])) + grid[y][x];
    }
}

cout << "dp: " << endl;
for(int y = 0; y < h; y++) cout << dp[y][w-1] << endl;

如您所见，在最后几行中，我正在打印 dp 数组的最后一列（我对此感兴趣）。当我添加以下语句时，就在 // 基本情况下方：

p[0][0] = 3;

我的 dp 数组发生了变化，我不知道为什么。我只添加了该语句，我想知道为什么 dp 数组会发生变化以及如何防止这种情况发生。

有人可以向我解释为什么会这样吗？

谢谢！

4

1 回答 1

8

您的代码具有未定义的行为。考虑以下循环中发生的情况y = 0：

for(int y = 0; y < h; y++)
{
    dp[y][x] = min(dp[y][x-1], min(dp[(y-1)%h][x-1], dp[(y+1)%h][x-1])) + grid[y][x];
                                   ^^^^^^^^^^^ out of bounds since -1%h equals -1

你的意思是说(y+h-1)%h代替(y-1)%h？

于 2013-01-19T18:45:41.217 回答