程式設計－從矩陣左上角走到右下角

題目要求：

編寫一個算法，在非負矩陣中，從左上角走到右下角，每次隻能向左或向下移動一格，輸出走過的路徑節點坐标和最小權值。

方法：動态規劃法

狀态轉移方程stat[i][j] = min{stat[i-1][j], stat[i][j-1]}。

邏輯：目的節點是從其上邊節點或左邊節點下來的，判斷上邊節點和左邊節點哪個小，就是從哪個節點下來的，并用一個direct矩陣記錄所來方向，若該節點是從上邊節點下來的，就将direct矩陣該節點定為1，否則定為0。

非負矩陣名字定義為matrix，這個matrix矩陣有兩條特殊路徑，即第一行和第一列，因為第一行的所有節點隻能從它左邊節點走過來的，而第一列的所有節點都是從它上一個節點走過來的。這樣，就能得到第一行每個節點到左上角節點的權值和第一列每個節點到左上角節點的權值。

比如：

（0， 0）（0，1）（0， 2）

（1， 0）（1，1）（1，2）

（2，0）（2， 1）（2，2）

對應的權值為：

1 2 3

4 5 6

2 3 5

節點（0，0）為起始點，節點（2，2）為終止點，從起始點到節點（0，1）的總權值為（0，0）的權值加上（0，1）的權值，從起始點到（0，2）的總權值為（0，0）的權值加上（0，1）的權值加上（0，2）的權值。同理可得（1，0）到起始點的總權值，（2，0）到起始點的總權值。

得到的stat表為

1 3 6

5

7

而（1，1）節點到起始點有兩個方向，一個是它的上邊，即（0，1）點，一個是它的左邊（1，0）點，通過stat表可知，（0，1）點的總權值為3，（1，0）點的總權值為5，因為要獲得最短路徑，是以我們選最小的權值3在加上目前節點的權值就是目前節點到啟始節點的總權值，即為8。為了記錄目前權值是從它上邊走過來的還是從它左邊走過來的，我們還第一了一個direct矩陣，初始化後的direct矩陣為：

0 1 1

其中，1表示該節點是從它的左邊走過來的，0表示該節點是從它上邊節點走過來的，在修改stat矩陣時，也應該修改direct矩陣。經過兩層循環，就能填充stat矩陣和direct矩陣，填充滿後的stat矩陣和direct矩陣為：

stat矩陣：

1 3 6

5 8 12

7 10 15

direct矩陣：

0 1 1

0 0 0

0 1 1

stat矩陣的終止頂點中的權值就是最短路徑的權值。

根據direct矩陣，我們能夠得到目的頂點（2， 2）是從它左邊頂點（2，1）走過來的，因為目前direct值為1（表示從目前頂點左邊走過來），而（2，1）是從它左邊頂點（2，0）走過來的，而（2，0）是從它上邊頂點（1，0）走過來的，而（1，0）又是從它上邊（0，0）點走過來的，而（0，0）點就是啟始頂點。

由此就得到了最短路徑和最短路徑權值，代碼如下：

# include <iostream>
# include <vector>

using namespace std;

void getPath(vector<vector<int> > &matrix, int &value, vector<int> &path_i, vector<int> &path_j)
{
    if(matrix.empty())
        return;
    int rows = matrix.size();
    int cols = matrix[].size();
    vector<vector<int> > stat(rows, vector<int> (cols));  // 用來存放已經過節點的總權值
    vector<vector<int> > direct(rows, vector<int> (cols)); // 用來存放該節點是從哪個方向來的(1表示從上邊,0表示從左邊)）
    int sum = ;
    for (int j = ; j < cols; ++j)  // 初始化狀态表第一行
    {
        sum += matrix[][j];
        stat[][j] = sum;
        direct[][j] = ;
    }
    sum = ;
    for (int i = ; i < rows; ++i)  // 初始化狀态表第一列
    {
        sum += matrix[i][];
        stat[i][] = sum;
        direct[i][] = ;
    }
    for (int i = ; i < rows; ++i)  // 填充狀态表和方向表
    {
        for (int j = ; j < cols; ++j)
        {
            if (stat[i - ][j] < stat[i][j - ])
            {
                stat[i][j] = stat[i - ][j] + matrix[i][j];
                direct[i][j] = ;
            }
            else
            {
                stat[i][j] = stat[i][j - ] + matrix[i][j];
                direct[i][j] = ;
            }
        }
    }

    value = stat[rows - ][cols - ];  // 擷取最短路徑權值
    for (int i = rows -, j = cols - ; i >=  && j >= ;)  // 獲得最短路徑
    {
            path_i.push_back(i);
            path_j.push_back(j);
            if (direct[i][j] == )
                j--;
            else
                i--;
    }
}
void printPath(vector<int> path_i, vector<int> path_j)  // 列印路徑
{
    for (int i = path_i.size() - ; i >= ; --i)
    {
        cout << '(' << path_i[i] << ", " << path_j[i] << ')' << endl;
    }
}

int main(void)
{
    int matrix_temp[][] = {{, , , , , , },
                            {, , , , , , },
                            {, , , , , , },
                            {, , , , , , },
                            {, , , , , , },
                            {, , , , , , }};
    vector<vector<int> > matrix;
    int rows = ;
    int cols = ;
    for (int i = ; i < rows; ++i)
    {
        vector<int> temp;
        for (int j = ; j < cols; ++j)
        {
            temp.push_back(matrix_temp[i][j]);
        }
        matrix.push_back(temp);
        temp.clear();
    }
    vector<int> path_i;  // 用來存放經過的節點的行号
    vector<int> path_j;  // 用來存放經過的節點的列号
    int value;           // 用來存放最短路徑的權值
    getPath(matrix, value, path_i, path_j);
    cout << "value is " << value << endl;
    cout << "path: " << endl;
    printPath(path_i, path_j);
}
           

若有不對之處，敬請指正。