C++未初始化二维数组导致避水坑路径计数结果异常的原因是什么

#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    const int MAXIMUM = 100;
    int paddlePosition = -1;

    int pos[MAXIMUM][MAXIMUM] {0};  //type 1
    //int pos[MAXIMUM][MAXIMUM];    //type 2
    for(auto puddle = puddles.begin(); puddle != puddles.end(); puddle++)
        pos[(*puddle)[1] - 1][(*puddle)[0] - 1] = paddlePosition;
    
    pos[0][0] = 1;
    for(int i = 1; i < m; i++)
        if(pos[0][i] != paddlePosition)
            pos[0][i] = pos[0][i - 1];
    for(int i = 1; i < n; i++)
        if(pos[i][0] != paddlePosition)
            pos[i][0] = pos[i - 1][0];
    
    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j < m; j++)
        {
            if(pos[i][j] == paddlePosition);
            else if(pos[i - 1][j] == paddlePosition && pos[i][j - 1] == paddlePosition)
                pos[i][j] = paddlePosition;
            else if(pos[i - 1][j] == paddlePosition)
                pos[i][j] = pos[i][j - 1];
            else if(pos[i][j - 1] == paddlePosition)
                pos[i][j] = pos[i - 1][j];
            else
                pos[i][j] = (pos[i - 1][j] + pos[i][j - 1]) % 1000000007;
        }
    }
    
    int answer = pos[n - 1][m - 1];
    if(answer == paddlePosition)
        answer = 0;
    return answer;
}

问题描述 #

上述代码仅存在一处差异：pos数组是否进行初始化。当传入参数m=100、n=100、puddles=[[1,1]]时，若使用未初始化的pos数组，访问pos[99][99]得到的是不确定的非固定值。我原本认为双重for循环是连续访问数据，且数组边界已经完成初始化，因此不初始化数组也不会影响结果，类似于懒加载的效果，但该假设不成立。请问两种写法结果不同的原因是什么？

原因分析 #

• C++中函数内部定义的非静态局部数组如果没有显式初始化，会分配在栈内存中，元素的值是内存之前残留的随机垃圾值，没有任何确定性。你用int pos[MAXIMUM][MAXIMUM] {0};的写法时，数组所有元素都会被自动零初始化，非水坑位置的初始值都是0，不会和你设定的水坑标记-1混淆，逻辑运行完全符合预期。
• 你的代码用-1作为水坑的唯一标记，只有puddles列表里的位置会被主动赋值为-1。如果使用未初始化的数组，任意位置都可能随机出现-1，这些位置会被误判为水坑，if(pos[i][j] == paddlePosition);判断命中后，后续所有赋值逻辑会被跳过，该位置的值不会被覆盖，后续依赖这个位置的路径数计算都会出错，最终结果自然是随机不确定的。
• 你所说的「懒加载」逻辑成立的前提是：所有未被主动赋值的初始值都不会触发逻辑分支的误判，显然随机垃圾值完全不满足这个前提，所以假设不成立。

内容的提问来源于stack exchange，提问作者신승빈