【題解】ZeroJudge e287: 機器人的路徑

題目敘述】https://zerojudge.tw/ShowProblem?problemid=e287
【解題想法】模擬機器人移動方向

  • 題目要求「從地圖中數值最低的那格出發」,讀入測資時順便找出「出發點」的座標。
  • 機器人移動的規律:不斷走向周圍的格子中數值最低且沒被走過的格子。
    • 設定上下左右四個移動方向:d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
    • check( ):檢查下一步的格子是否超出界線。
    • a[i][j] = -1:把走過的格子設為 -1,避免重複走訪。
#include <iostream>
using namespace std;

int n, m, a[105][105], ni, nj, mn = 1000000, ans, nxt;
int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

bool check(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 >> a[i][j];
            if (a[i][j] < mn){
                mn = a[i][j];
                ni = i;
                nj = j;
            }
        }
    }
    ans += a[ni][nj];
    a[ni][nj] = -1;
    while (1){
        mn = 1000000;
        nxt = -1;
        for (int i = 0; i < 4; i++){
            if (check(ni+d[i][0], nj+d[i][1]) && a[ni+d[i][0]][nj+d[i][1]] != -1 && a[ni+d[i][0]][nj+d[i][1]] < mn){
                nxt = i;
                mn = a[ni+d[i][0]][nj+d[i][1]];
            }
        }
        if (nxt == -1) break;
        ni += d[nxt][0];
        nj += d[nxt][1];
        ans += a[ni][nj];
        a[ni][nj] = -1;
    }
    cout << ans << "\n";
}

Python 程式碼 (credit: Amy Chou)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while True:
    try:
        n, m = map(int, input().split())
        a = [[0 for j in range(m)] for i in range(n)]
        x0 = -1
        y0 = -1
        z0 = 1000000
        for i in range(n):
            N = list(map(int, input().split()))
            for j, k in enumerate(N):
                a[i][j] = k
                if (k < z0):
                    x0 = i
                    y0 = j
                    z0 = k
        
        ans = 0
        ex = [[0 for j in range(m)] for i in range(n)]
        while (z0 < 1000000):
            ex[x0][y0] = 1
            ans += z0
            nxt_x = -1
            nxt_y = -1
            nxt_z = 1000000
            for i in range(4):
                nx = x0 + dx[i]
                ny = y0 + dy[i]
                if (nx >= 0) and (nx < n) and (ny >= 0) and (ny < m):
                    if (ex[nx][ny] == 0) and (a[nx][ny] < nxt_z):
                        nxt_x = nx
                        nxt_y = ny
                        nxt_z = a[nx][ny]
                        
            x0 = nxt_x
            y0 = nxt_y
            z0 = nxt_z

        print(ans)
    except:
        break
分享本文 Share with friends