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 に答える