機器人路徑

題目說明

這個題目是求一個路徑，會沿著整個地圖中最小值出發，一路沿著周圍的最小值走，直到沒有路為止。最後輸出沿路的總和即可。概念上我們只需要開一個二維陣列來存放地圖，然後定位到其中最小的值，然後開始加上每一次移動的位置數值。值得注意的是我們需要做越界檢測以及重複路徑檢測。

解題過程

在決定好解題概念後，第一步都是依據題目讀入資料。值得注意的是我們外加使用 mn 來記錄地圖當中的最小值，以及對應的 x 和 y 座標。

cin >> n >> m;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> v[i][j];
        if (v[i][j] < mn) {
            mn = v[i][j];
            y = i;
            x = j;
        }
    }
}

在讀入整個地圖後，要將起始點資料做處理。我們使用 o 來記錄路徑加總，而 x 和 y 分別代表地圖座標的定位點。當資料都獲取完後，我們要將點改成任意大於 1000001 的數字，我們這邊選用 1000002 來當作標記，來檢測走過的路徑。

o = v[y][x];
v[y][x] = 1000002;

接著我們要來處理每一次移動的檢測。簡單來說我們每次都要嘗試上下左右四種移動方式，並選擇當中數值最小的路去走。在這過程中我們需要確保不會嘗試移動到地圖範圍外，為了程式碼可讀性我選擇撰寫一個函式 in_range(y, x) 來處理範圍檢測，這個函式我們先設計好即可，稍後在實際實作。 mn 是用來紀錄可選路線的最小值， nxt 則是記錄下一個移動的方向。

mn = 1000001;
int nxt = -1;
if (in_range(y-1, x) && v[y-1][x] < mn) {
    nxt = 0;
    mn = v[y-1][x];
}

現在我們來撰寫 in_range(y, x) 這個函式。其實這個函式不會很複雜，就是對四個方向都做範圍檢測即可。當然你也可以不要用自訂函式，直接將對應的檢測寫入判斷式中即可。

bool in_range(int x, int y) {
    if (0 <= x && x < n && 0 <= y && y < m) return true;
    return false;
}

有了這些基本元素後，我們要將四個方向實際寫出來。另外還要讓每一次確定移動方向後，分別加上該點位置、更新定位點、標記舊位置等。最後由於不確定要走幾遍才會結束，所以要將整個流程放進一個無限迴圈中。

while (1) {
    mn = 1000001;
    int nxt = -1;

    if (in_range(y-1, x) && v[y-1][x] < mn) {
        nxt = 0;
        mn = v[y-1][x];
    }
    if (in_range(y, x+1) && v[y][x+1] < mn) {
        nxt = 1;
        mn = v[y][x+1];
    }
    if (in_range(y+1, x) && v[y+1][x] < mn) {
        nxt = 2;
        mn = v[y+1][x];
    }
    if (in_range(y, x-1) && v[y][x-1] < mn) {
        nxt = 3;
        mn = v[y][x-1];
    }
    
    y += d[nxt][0];
    x += d[nxt][1];
    o += v[y][x];
    v[y][x] = 1000002;
}

最後根據題目敘述，如果四個方向皆不能移動，即結束程式輸出答案。於是我們在無限迴圈中添加結束的判斷式，即檢測移動方向 nxt 是否為初始值 -1。

while(1) {
    ...

    if (nxt == -1) break;

    ...
}

cout << o << "\n";

解題成果

#include <iostream>
using namespace std;

int n, m;
int v[105][105];
int y, x;
int mn = 1000001;
int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int o = 0;

bool in_range(int x, int y) {
    if (0 <= x && x < n && 0 <= y && y < m) return true;
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
            if (v[i][j] < mn) {
                mn = v[i][j];
                y = i;
                x = j;
            }
        }
    }

    o = v[y][x];
    v[y][x] = 1000002;
    while (1) {
        mn = 1000001;
        int nxt = -1;

        if (in_range(y-1, x) && v[y-1][x] < mn) {
            nxt = 0;
            mn = v[y-1][x];
        }
        if (in_range(y, x+1) && v[y][x+1] < mn) {
            nxt = 1;
            mn = v[y][x+1];
        }
        if (in_range(y+1, x) && v[y+1][x] < mn) {
            nxt = 2;
            mn = v[y+1][x];
        }
        if (in_range(y, x-1) && v[y][x-1] < mn) {
            nxt = 3;
            mn = v[y][x-1];
        }
        
        if (nxt == -1) break;
        y += d[nxt][0];
        x += d[nxt][1];
        o += v[y][x];
        v[y][x] = 1000002;
    }

    cout << o << "\n";
}