Я пытаюсь напечатать максимальный возрастающий путь в матрице, но код продолжает выдавать ошибку времени выполнения - PullRequest
Новая
       29

Я пытаюсь напечатать максимальный возрастающий путь в матрице, но код продолжает выдавать ошибку времени выполнения

2 голосов
/ 01 августа 2020 
#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;
}

1 Ответ

2 голосов
/ 01 августа 2020

in 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 $
...