題目說明#
這個題目是求一個路徑，會沿著整個地圖中最小值出發，一路沿著周圍的最小值走，直到沒有路為止。最後輸出沿路的總和即可。概念上我們只需要開一個二維陣列來存放地圖，然後定位到其中最小的值，然後開始加上每一次移動的位置數值。值得注意的是我們需要做越界檢測以及重複路徑檢測。
解題過程#
在決定好解題概念後，第一步都是依據題目讀入資料。值得注意的是我們外加使用 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";
}
