[zerojudge] e287: 機器人的路徑

題目連結：

e287: 機器人的路徑

題意：

給一個 $n \ * \ m$ 大小的地圖，

從最小值開始走，

不斷走向周圍的格子中數值最低且沒被走過的格子，

直到它沒有路可以走，

輸出路徑上數字總和。

解題策略：

在讀取測資時，

即可先找到最小值的的點座標，

從該位置開始一直往周圍找路，

並且將經過的格子記為已拜訪且累加該格的數字，

直到沒有移動，

最後輸出答案即可。

程式碼參考：

$C++$：

$JUDGE\_RESULT$：$AC \ (4ms, \ 404KB)$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(false), cin.tie(nullptr);
#define endl '\n'
using namespace std;

struct point {
    int x, y, mn; // x 座標, y 座標, min 最小值
    point(int _x = 0, int _y = 0): mn(numeric_limits<int>::max()), x(_x), y(_y) {}
};

struct table {
    // 也可以用 vector<vector<pair<int, bool>>> 但相對不直觀
    vector<vector<int>> data; // 地圖資料
    vector<vector<bool>> visit; // 記錄有沒有走過
    table(int n = 0, int m = 0) {
        data.resize(n, vector<int>(m));
        visit.resize(n, vector<bool>(m));
    }
};

int main() { _
    int n, m, ans = 0;
    cin >> n >> m;
    point cur, next;
    table mp(n, m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp.data[i][j];
            if (mp.data[i][j] < cur.mn) // 取得最小值的 x 座標, y 座標, min
                cur.mn = mp.data[i][j], cur.x = i, cur.y = j;
        }
    }
    bool moving = true;
    next = cur;
    while (moving) { // 如果還有移動
        ans += mp.data[cur.x][cur.y]; // 累加路徑上數字
        moving = false; // 假設沒有下一步
        mp.visit[cur.x][cur.y] = true; // 已拜訪過該點
        next.mn = numeric_limits<int>::max(); // 先設為最大值以便找周圍最小值
        // 嘗試往上下左右找
        // 其中有路的話就更新且設 moving 為 true
        if (cur.x + 1 < n && !mp.visit[cur.x + 1][cur.y]) { // 沒有超過右界且未拜訪過
            if (mp.data[cur.x + 1][cur.y] < next.mn)
                next.x = cur.x + 1, next.y = cur.y, next.mn = mp.data[cur.x + 1][cur.y], moving = true;
        }
        if (cur.x - 1 >= 0 && !mp.visit[cur.x - 1][cur.y]) { // 沒有超過左界且未拜訪過
            if (mp.data[cur.x - 1][cur.y] < next.mn)
                next.x = cur.x - 1, next.y = cur.y, next.mn = mp.data[cur.x - 1][cur.y], moving = true;
        }
        if (cur.y + 1 < m && !mp.visit[cur.x][cur.y + 1]) { // 沒有超過下界且未拜訪過
            if (mp.data[cur.x][cur.y + 1] < next.mn)
                next.x = cur.x, next.y = cur.y + 1, next.mn = mp.data[cur.x][cur.y + 1], moving = true;
        }
        if (cur.y - 1 >= 0 && !mp.visit[cur.x][cur.y - 1]) { // 沒有超過上界且未拜訪過
            if (mp.data[cur.x][cur.y - 1] < next.mn)
                next.x = cur.x, next.y = cur.y - 1, next.mn = mp.data[cur.x][cur.y - 1], moving = true;
        }
        cur = next;
    }
    cout << ans << endl;
}

$PYTHON$：

$JUDGE\_RESULT$：$AC \ (32ms, \ 4.6MB)$

from sys import stdin
from copy import copy

limit = 2147483647
class point:
    def __init__(self, x = 0, y = 0):
        self.x = x # x 座標
        self.y = y # y 座標
        self.mn = limit # min 最小值

n, m = [int(x) for x in stdin.readline().strip().split()]
mp = [] # 地圖資料
visit = [[0] * m for _ in range(n)] # 記錄有沒有走過
cur = point()
for i in range(n):
    data = [int(x) for x in stdin.readline().strip().split()]
    for j in range(len(data)):
        if data[j] < cur.mn: # 取得最小值的 x 座標, y 座標, min
            cur.mn, cur.x, cur.y = data[j], i, j
    mp.append(data)

moving = True
ans = 0
nxt = copy(cur)

while moving: # 如果還有移動
    ans += mp[cur.x][cur.y] # 累加路徑上數字
    moving = False # 假設沒有下一步
    visit[cur.x][cur.y] = True # 已拜訪過該點
    nxt.mn = limit # 先設為最大值以便找周圍最小值
    '''
    嘗試往上下左右找
    其中有路的話就更新且設 moving 為 true
    '''
    if cur.x + 1 < n and not visit[cur.x + 1][cur.y]: # 沒有超過右界且未拜訪過
        if mp[cur.x + 1][cur.y] < nxt.mn:
            nxt.x, nxt.y, nxt.mn = cur.x + 1, cur.y, mp[cur.x + 1][cur.y]
            moving = True
    if cur.x - 1 >= 0 and not visit[cur.x - 1][cur.y]: # 沒有超過左界且未拜訪過
        if mp[cur.x - 1][cur.y] < nxt.mn:
            nxt.x, nxt.y, nxt.mn = cur.x - 1, cur.y, mp[cur.x - 1][cur.y]
            moving = True
    if cur.y + 1 < m and not visit[cur.x][cur.y + 1]: # 沒有超過下界且未拜訪過
        if mp[cur.x][cur.y + 1] < nxt.mn:
            nxt.x, nxt.y, nxt.mn = cur.x, cur.y + 1, mp[cur.x][cur.y + 1]
            moving = True
    if cur.y - 1 >= 0 and not visit[cur.x][cur.y - 1]: # 沒有超過上界且未拜訪過
        if mp[cur.x][cur.y - 1] < nxt.mn:
            nxt.x, nxt.y, nxt.mn = cur.x, cur.y - 1, mp[cur.x][cur.y - 1]
            moving = True
    cur = copy(nxt)

print(ans)

以上，
若有更好的想法歡迎提出哦！