Tìm đường đi để nhặt được nhiều đồng xu nhất

Cho ma trận mxn (m,n <=40), các giá trị trong ma trận từ 0->9, ngoại trừ điểm {0,0} và {n-1,m-1} có giá trị 1->9. Yêu cầu là đi từ {0,0} đến {n-1,m-1}. Chỉ đi được từ trái qua phải hoặc từ trên xuống, không được đi chéo và không được đi vào giá trị số 0. Phần Output cần chỉ ra số đồng xu tối đa lụm được và đường đi để lụm được số đồng xu đó. Nếu không thể đi được thì xuất ra thông báo ma trận không có lối ra.

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

struct toaDo{
    int x;
    int y;
};

struct giaTri{
    int coin;
    int giaTriDuongDi;
    toaDo duongDiB[1000];
};

int a[50][50];
int n,m;
giaTri ketqua[1000];
int soCachDi=0;
toaDo duongDi[1000];
bool kiemtra=false;


void createData();
void inputData();
int tTry(int x,int y,int coin,int diaDiem);
void saveResult(int coin,toaDo duongDi[],int diaDiem);
void outputDuongDi(toaDo duongDiB[],int diaDiem);

int main()
{
    srand(time(NULL));
    createData();
    inputData();
    tTry(0,0,0,0);
    int maxi=0;
    for(int i=1;i<soCachDi;i++){
        if(ketqua[maxi].coin<ketqua[i].coin){
            maxi=i;
        }
    }
    if(!kiemtra){
        cout << "Ma Tran khong co loi ra.
";
    }
    else{
        cout << "So coin lon nhat co the lum duoc la: " << ketqua[maxi].coin << endl;
        cout << "Duong di de co duoc so coin lon nhat la: ";
        outputDuongDi(ketqua[maxi].duongDiB,ketqua[maxi].giaTriDuongDi);
    }
    return 0;
}
//Lấy dữ liệu từ file txt
void inputData(){
    fstream f;
    f.open("InputData.txt",ios::in);
    if(!f.is_open()){
        cout << "File du lieu khong ton tai.";
        system("exit");
    }
    f >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            f >> a[i][j];
        }
    }
    f.close();
}
//Thuật toán quay lui
int tTry(int x,int y,int coin,int diaDiem){
    bool flag=true;
    if(a[x][y+1] > 0){            //Nếu giá trị bên phải của nó >0 là có thể đi được
        coin+=a[x][y+1];
        duongDi[diaDiem].x=x;    //Lưu tọa độ điểm đang ở
        duongDi[diaDiem].y=y;
        diaDiem++;
        flag=false;                     
        tTry(x,y+1,coin,diaDiem);
    }
    if(a[x+1][y] > 0){
        if(!flag){               //Khi quay ngược lại thì coin cần phải trừ bớt do phần ở trên cộng thêm
            coin-=a[x][y+1];
            diaDiem--;
        }
        coin+=a[x+1][y];
        duongDi[diaDiem].x=x;
        duongDi[diaDiem].y=y;
        diaDiem++;
        tTry(x+1,y,coin,diaDiem);
    }
    if(x==(n-1) && y==(m-1)){          //Xét xem đi tới điểm ra ma trận
        coin+=(a[0][0]);
        saveResult(coin,duongDi,diaDiem);
    }
    return 0;
}
//Lưu lại đường đi để ra ma trận và số coin lụm được từ đường đi đó
void saveResult(int coin, toaDo duongDi[],int diaDiem){
    ketqua[soCachDi].coin = coin;
    ketqua[soCachDi].giaTriDuongDi = diaDiem;
    for(int i=0;i<diaDiem;i++){
        ketqua[soCachDi].duongDiB[i] = duongDi[i];
    }
    soCachDi++;
    kiemtra=true;
}
//Xuất ra đường đi
void outputDuongDi(toaDo duongDiB[],int diaDiem){
    for(int i=0;i<diaDiem;i++){
        cout << "{" << duongDiB[i].x << "," << duongDiB[i].y << "} -> ";
    }
    cout << endl;
}
//Tạo ma trận
void createData(){
    int x,y;
    x= rand()%40+1;
    y= rand()%40+1;
    fstream f;
    f.open("InputData.txt",ios::out);
    f << x << " " << y << endl;
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            if((i==0 && j==0) || (i==x-1 && j==y-1)){
                f << rand()%9+1 << " ";
                continue;
            }
            f << rand()%10 << " ";
        }
        f << endl;
    }
    f.close();
    cout << "Ma tran da duoc tao ra va luu vao file InputData.txt
";
}

Đây là code của mình. Hiện mình dùng thuật toán quay lui. Với ma trận nhỏ thì còn chạy ra chứ ma trận lớn là nó tắt thở rồi. Ai có cách nào khác giúp mình tối ưu nó hơn tý.

Nhờ sự hướng dẫn của @JuniorK mà mình đã tối ưu được bài này hơn, với thuật toán quay lui thì mình chỉ có thể tìm trong ma trận tầm <40, còn với cái này thì mình có thể tìm hơn đến 1000. Hiện tại ở các ma trận nhiều thì mình vẫn chưa kiểm tra hết được xem là có đúng hay không. Ở dưới mình sẽ post code của mình, mọi người có thể góp ý thêm giúp mình.

p/s: Mình không có search cái truy vết trên google. Mà nghĩ ra cái đó nên làm trước.

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

struct toaDo
{
    int x;
    int y;
};

int a[1000][1000];
int sum[1000][1000];
int n,m;
int soCachDi=0;
toaDo duongDi[100000];
bool kiemtra=true;


void createData();
void inputData();
void quyHoachDong();
void truyVet();

int main()
{
    srand(time(NULL));
    createData();
    inputData();
    cout << "Bat dau giai ma tran.
";
    quyHoachDong();
    cout << "Da giai xong ma tran.
";
    return 0;
}

void inputData()
{
    cout << "Dang lay du lieu.....
";
    fstream f;
    f.open("InputData.txt",ios::in);
    if(!f.is_open())
    {
        cout << "File du lieu khong ton tai.";
        system("exit");
    }
    f >> n >> m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            f >> a[i][j];
        }
    }
    f.close();
    cout << "Da doc xong du lieu.
";
}

void createData()
{
    int x,y;
    x= rand()%999+1;
    y= rand()%999+1;
    fstream f;
    f.open("InputData.txt",ios::out);
    f << x << " " << y << endl;
    for(int i=1; i<=x; i++)
    {
        for(int j=1; j<=y; j++)
        {
            if((i==1 && j==1) || (i==x && j==y))
            {
                f << rand()%9+1 << " ";
                continue;
            }
            f << rand()%10 << " ";
        }
        f << endl;
    }
    f.close();
    cout << "Ma tran da duoc tao ra va luu vao file InputData.txt
";
}

void quyHoachDong()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(i==1 && j==1){
                sum[i][j] = a[i][j];
            }
            else if(i==1){
                sum[i][j] = a[i][j] + sum[i][j-1];
            }
            else if(j==1){
                sum[i][j] = a[i][j] + sum[i-1][j];
            }
            else if(a[i][j-1]!=0 || a[i-1][j]!=0)
                sum[i][j] = a[i][j] + (sum[i-1][j] > sum[i][j-1] ? sum[i-1][j] : sum[i][j-1]);
        }
    }
    if(sum[n][m]==0){
        cout << "Ma tran khong co loi ra.
";
    }
    else{
        cout << "So coin lon nhat co the nhan duoc la: " << sum[n][m] << endl;
        cout << "Duong di de co duoc so coin lon nhat: ";
        truyVet();
    }
}

void truyVet()
{
    int test;
    int i=n,j=m;
    while(i>1 || j>1)
    {
        test=sum[i][j] - a[i][j];
        if(test==sum[i-1][j])
        {
            duongDi[soCachDi].x=i;
            duongDi[soCachDi].y=j;
            soCachDi++;
            i--;
        }
        else
        {
            duongDi[soCachDi].x=i;
            duongDi[soCachDi].y=j;
            soCachDi++;
            j--;
        }
    }
    cout << "{1,1} -> ";
    for(i=soCachDi-1; i>0; i--)
    {
        cout << "{" << duongDi[i].x << "," << duongDi[i].y << "} -> ";
    }
    cout << "{" << duongDi[i].x << "," << duongDi[i].y << "}";
    cout << endl;
}