//
//  main.cpp
//  test_
//
//  Created by 杜辉锋 on 2022/10/20.

#include <iostream>
#include <vector>
#include <math.h>

int getShortestPath(std::vector<std::vector<int>>&vecGrids,std::vector<std::vector<int>>&vecScore,int m, int n)
{
    for(int i =0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i ==0 && j == 0)
            {
                vecScore[i][j] = vecGrids[i][j];
            }
            else {
                if(i == 0)
                {
                    vecScore[i][j] = vecScore[i][j-1] + vecGrids[i][j];
                }
                else if(j == 0)
                {
                    vecScore[i][j] = vecScore[i-1][j] + vecGrids[i][j];
                }
                else {
                    vecScore[i][j] = std::min(vecScore[i][j-1] + vecGrids[i][j],vecScore[i-1][j] + vecGrids[i][j]);
                }
            }
        }
    }
    return vecScore[m-1][n-1];
}

/**
 *  6,3,2,2,4
 *  6,3,2,2,4
 *  6,3,2,2,4
 *  6,3,2,2,4
 *  6,3,2,2,4
 **/


int main(int argc, const char * argv[]) {
    std::vector<std::vector<int>> vecTest;
    std::vector<int> vecInfo = {6,3,2,2,4};
    vecTest.push_back(vecInfo);
    vecTest.push_back(vecInfo);
    vecTest.push_back(vecInfo);
    vecTest.push_back(vecInfo);
    vecTest.push_back(vecInfo);
    std::vector<std::vector<int>> vecScore(vecTest);
    int nMinValue = getShortestPath(vecTest,vecScore,5, 5);
    std::cout << "the MinShortestPath:" << nMinValue << std::endl;
    return 0;
}