c++ - 我正在尝试打印矩阵中的最大递增路径，但代码不断给出运行时错误

Question

#include<bits/stdc++.h>
using namespace std;

vector<vector<int> > dp;

int cal(int i , int j , int m , int n , int prev , vector<vector<int>>& matrix) {
    if(i<0 || j<0 || matrix[i][j] <= prev || j>=n || i>=m)
        return 0;
    
    if(dp[i][j] != -1)
        return dp[i][j];
    int ans = 0;
    int now = matrix[i][j];
    
    ans = max(ans , cal(i-1,j,m,n,now,matrix));
    ans = max(ans , cal(i+1,j,m,n,now,matrix));
    ans = max(ans , cal(i,j-1,m,n,now,matrix));
    ans = max(ans , cal(i,j+1,m,n,now,matrix));
    
    dp[i][j] = 1+ans;
    return dp[i][j];
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n , m;
    cin >> n >> m;
    vector<vector<int> > matrix;
    matrix.assign(n , vector<int>(m,0));
    for(int i=0 ; i<n ; ++i) {
        for(int j=0 ; j<m ; ++j) {
            cin >> matrix[i][j];
        }
    }
    dp.assign(matrix.size() , vector<int>(matrix[0].size() , -1));

    for(int i=0 ; i<n ; ++i) {
        for(int j=0 ; j<m ; ++j) {
            cout<<cal(i,j,n,m,-1,matrix)<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Answer 1

在 cal 中，您的支票在行中的顺序错误:

if(i<0 || j<0 || matrix[i][j] <= prev || j>=n || i>=m)

它必须是这样的:

if(i<0 || j<0 || j>=n || i>=m || matrix[i][j] <= prev)

不以未定义的行为访问矩阵之外

之后，编译和执行:

pi@raspberrypi:/tmp $ g++ -Wall c.cc
pi@raspberrypi:/tmp $ cat input.txt 
2 2
10 11
20 21
pi@raspberrypi:/tmp $ ./a.out
pi@raspberrypi:/tmp $ cat output.txt 
3 2 
2 1 
pi@raspberrypi:/tmp $ valgrind ./a.out
==3983== Memcheck, a memory error detector
==3983== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3983== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==3983== Command: ./a.out
==3983== 
==3983== 
==3983== HEAP SUMMARY:
==3983==     in use at exit: 122,880 bytes in 6 blocks
==3983==   total heap usage: 15 allocs, 9 frees, 143,200 bytes allocated
==3983== 
==3983== LEAK SUMMARY:
==3983==    definitely lost: 0 bytes in 0 blocks
==3983==    indirectly lost: 0 bytes in 0 blocks
==3983==      possibly lost: 0 bytes in 0 blocks
==3983==    still reachable: 122,880 bytes in 6 blocks
==3983==         suppressed: 0 bytes in 0 blocks
==3983== Rerun with --leak-check=full to see details of leaked memory
==3983== 
==3983== For lists of detected and suppressed errors, rerun with: -s
==3983== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
pi@raspberrypi:/tmp $