【題目敘述】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