# APCS實作題2019年6月第2題：機器人的路徑
> 第1版：2023年9月9日
> 第2版：2025年1月6日，新增 BFS 的寫法
> 作者：王一哲
> 題目來源：108年6月實作題第2題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=e287)
<br />
## 題目
### 問題描述
你有一台機器人，它會在地上爬。經過了8756天的觀察過後，你發現了它移動的規律。它會從地圖中數值最低的那格出發，然後不斷走向周圍的格子中數值最低且沒被走過的格子。直到它沒有路可以走。(周圍的定義是上下左右，共4格)
<br />
### 輸入格式
單筆輸入
第一行有
兩個數字 n, m 代表地圖的大小
接著有 n 行，每行有 m 個數字，用空白隔開
每個數字都非負且小於 1000000 且都不相等
<br />
### 輸出格式
輸出路徑上的數字總和
<br />
### 範例：輸入
```
1 7
1 2 3 4 5 6 7
```
### 範例：正確輸出
```
28
```
<br />
## Python 程式碼
### 寫法1，簡單直接的作法
於 ZeroJudge 測試結果，最長運算時間約為 24 ms，使用記憶體最多約為 3.9 MB，通過測試。
```python=
n, m = map(int, input().split()) # 讀取地圖y方向長度n、x方向寬度m
visited = [[False]*m for _ in range(n)] # 格子被走訪過的狀態
data = [] # 格子數值資料
now, x, y = 1000000, 0, 0 # 目前格字數值，x座標，y座標
for i in range(n): # 讀取 n 行資料
tmp = list(map(int, input().split())) # 用空格分隔資料，暫存為 tmp
data.append(tmp) # 將 tmp 加入 data
mintmp = min(tmp) # 找出 tmp 中的最小值
if mintmp < now: # 如果 mintmp 小於 now
y = i # y座標更新為i
x = tmp.index(mintmp) # x座標更新為 mintmp 於 tmp 的索引值
now = mintmp # now 更新為 mintmp
visited[y][x] = True # (y, x) 格子被走訪過
ans = data[y][x] # 答案 ans 設定為 data[y][x]
flag = True # 繼續執行程式的狀態 flag 設定為 True
while flag:
val = [1000000]*4 # 週圍4格的值，預設為測資格子最大值 1000000
s0, s1, s2, s3 = False, False, False, False # 週圍4格是否可以被走訪的狀態
# 左側格子
if x-1 >= 0 and not visited[y][x-1]:
val[0] = data[y][x-1]
s0 = True
# 右側格子
if x+1 < m and not visited[y][x+1]:
val[1] = data[y][x+1]
s1 = True
# 上方格子
if y-1 >= 0 and not visited[y-1][x]:
val[2] = data[y-1][x]
s2 = True
# 下方格子
if y+1 < n and not visited[y+1][x]:
val[3] = data[y+1][x]
s3 = True
# 如果週圍4格任一格可被走訪，找出 val 最小值，更新 ans、x、y、visited
if s0 or s1 or s2 or s3:
minval = min(val)
ans += minval
idx = val.index(minval)
if idx == 0:
visited[y][x-1] = True
x = x-1
elif idx == 1:
visited[y][x+1] = True
x = x+1
elif idx == 2:
visited[y-1][x] = True
y = y-1
elif idx == 3:
visited[y+1][x] = True
y = y+1
else: # 如果週圍4格任一格皆不可走訪，flag 設定為 False，終止 while 迴圈
flag = False
print(ans) # 印出答案
```
<br />
### 寫法2，BFS，使用 list 儲存待走訪節點
於 ZeroJudge 測試結果，最長運算時間約為 24 ms，使用記憶體最多約為 3.9 MB，通過測試。
```python=
n, m = map(int, input().split()) # 地圖維度 n*m
graph = [] # 地圖
now = 10000000 # 目前的最小值，預設為大於題目範圍的值
sr, sc = 0, 0 # 起點，預設為 (0, 0)
for i in range(n): # 讀取 n 行資料
row = list(map(int, input().split())) # 讀取一行資料
graph.append(row) # 加到 graph
imin = min(row) # 此行中的最小值
if imin < now: # 如果 imin < now
now = imin # 更新 now
sr, sc = i, row.index(imin) # 更新起點座標
# end of for loop
que = [[sr, sc]] # 待走訪節點
head = 0 # 從 que 讀取資料的索引值
total = 0 # 加總
visit = [[False]*m for _ in range(n)] # 走訪狀態
# BFS
while head < len(que): # 如果 head 還沒有出界繼續執行
r, c = que[head]; head += 1 # 從 que 讀取座標 (r, c)，head 加 1
visit[r][c] = True # 已走訪 (r, c)
total += graph[r][c] # 更新 total
imin = 10000000 # 暫存最小值的變數
for dr, dc in ((0, 1), (-1, 0), (0, -1), (1, 0)): # 四方向檢測
nr, nc = r+dr, c+dc # 要測試的座標 (nr, nc)
if nr < 0 or nr >= n or nc < 0 or nc >= m: continue # 如果 (nr, nc) 已出界，檢測下一個點
if visit[nr][nc]: continue # 如果 (nr, nc) 已走訪，檢測下一個點
if graph[nr][nc] < imin: # 如果 (nr, nc) 的值小於 imin
if imin == 10000000: que.append([nr, nc]) # 如果 imin 等於 10000000，找到四方向中第一個值，[nr, nc] 加入 que
else: que[-1] = [nr, nc] # 否則取代 que 最後一項
imin = graph[nr][nc] # 更新 imin
# 結束四方向檢測
# end of while loop
print(total) # 印出答案
```
<br />
### 寫法3，BFS，使用 deque 儲存待走訪節點
於 ZeroJudge 測試結果，最長運算時間約為 28 ms，使用記憶體最多約為 4.2 MB，通過測試。
```python=
from collections import deque
n, m = map(int, input().split()) # 地圖維度 n*m
graph = [] # 地圖
now = 10000000 # 目前的最小值，預設為大於題目範圍的值
sr, sc = 0, 0 # 起點，預設為 (0, 0)
for i in range(n): # 讀取 n 行資料
row = list(map(int, input().split())) # 讀取一行資料
graph.append(row) # 加到 graph
imin = min(row) # 此行中的最小值
if imin < now: # 如果 imin < now
now = imin # 更新 now
sr, sc = i, row.index(imin) # 更新起點座標
# end of for loop
que = deque(); que.append([sr, sc]) # 待走訪節點
total = 0 # 加總
visit = [[False]*m for _ in range(n)] # 走訪狀態
# BFS
while que: # 如果 que 還有資料繼續執行
r, c = que.popleft() # 從 que 最前面讀取並移除資料
visit[r][c] = True # 已走訪 (r, c)
total += graph[r][c] # 更新 total
imin = 10000000 # 暫存最小值的變數
for dr, dc in ((0, 1), (-1, 0), (0, -1), (1, 0)): # 四方向檢測
nr, nc = r+dr, c+dc # 要測試的座標 (nr, nc)
if nr < 0 or nr >= n or nc < 0 or nc >= m: continue # 如果 (nr, nc) 已出界，檢測下一個點
if visit[nr][nc]: continue # 如果 (nr, nc) 已走訪，檢測下一個點
if graph[nr][nc] < imin: # 如果 (nr, nc) 的值小於 imin
if imin == 10000000: que.append([nr, nc]) # 如果 imin 等於 10000000，找到四方向中第一個值，[nr, nc] 加入 que
else: que[-1] = [nr, nc] # 否則取代 que 最後一項
imin = graph[nr][nc] # 更新 imin
# 結束四方向檢測
# end of while loop
print(total) # 印出答案
```
<br /><br />
## C++ 程式碼
### 寫法1，簡單直接的作法
於 ZeroJudge 測試結果，最長運算時間約為 12 ms，使用記憶體最多約為 368 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, m; // 讀取地圖y方向長度n、x方向寬度m
cin >> n >> m;
bool visited[n][m]; // 格子被走訪過的狀態，預設為 false
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
visited[i][j] = false;
}
}
unsigned int data[n][m]; // 格子數值資料
unsigned int now = 1000000; // 目前格字數值
int x = 0, y = 0; // x座標，y座標
for(int i=0; i<n; i++) { // 讀取 n 行資料
unsigned int tmp[m];
for(int j=0; j<m; j++) { // 用空格分隔資料，暫存為 tmp
cin >> tmp[j];
data[i][j] = tmp[j]; // 將 tmp[j] 加入 data
}
unsigned int mintmp = *min_element(tmp, tmp+m); // 找出 tmp 中的最小值
if (mintmp < now) { // 如果 mintmp 小於 now
y = i; // y座標更新為i
x = find(tmp, tmp+m, mintmp) - tmp; // x座標更新為 mintmp 於 tmp 的索引值
now = mintmp; // now 更新為 mintmp
}
}
visited[y][x] = true; // (y, x) 格子被走訪過
unsigned int ans = data[y][x]; // 答案 ans 設定為 data[y][x]
bool flag = true; // 繼續執行程式的狀態 flag 設定為 True
while(flag) {
unsigned int val[4]; // 週圍4格的值，預設為測資格子最大值 1000000
for(size_t i=0; i<4; i++) {
val[i] = 1000000;
}
// 週圍4格是否可以被走訪的狀態
bool s0 = false, s1 = false, s2 = false, s3 = false;
// 左側格子
if (x-1 >= 0 && !visited[y][x-1]) {
val[0] = data[y][x-1];
s0 = true;
}
// 右側格子
if (x+1 < m && !visited[y][x+1]) {
val[1] = data[y][x+1];
s1 = true;
}
// 上方格子
if (y-1 >= 0 && !visited[y-1][x]) {
val[2] = data[y-1][x];
s2 = true;
}
// 下方格子
if (y+1 < n && !visited[y+1][x]) {
val[3] = data[y+1][x];
s3 = true;
}
// 如果週圍4格任一格可被走訪，找出 val 最小值，更新 ans、x、y、visited
if (s0 || s1 || s2 || s3) {
unsigned int minval = *min_element(val, val+4);
ans += minval;
unsigned int idx = find(val, val+4, minval) - val;
if (idx == 0) {
visited[y][x-1] = true;
x = x-1;
} else if (idx == 1) {
visited[y][x+1] = true;
x = x+1;
} else if (idx == 2) {
visited[y-1][x] = true;
y = y-1;
} else if (idx == 3) {
visited[y+1][x] = true;
y = y+1;
}
} else { // 如果週圍4格任一格皆不可走訪，flag 設定為 False，終止 while 迴圈
flag = false;
}
}
cout << ans << endl; // 印出答案
return 0;
}
```
<br />
### 寫法2，BFS，使用 vector 儲存待走訪節點
於 ZeroJudge 測試結果，最長運算時間約為 4 ms，使用記憶體最多約為 408 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m; // 地圖維度 n*m
vector<vector<int>> graph (n, vector<int> (m, 0)); // 地圖
int now = 10000000, sr = 0, sc = 0; // 目前的最小值，預設為大於題目範圍的值；起點，預設為 (0, 0)
for(int i=0; i<n; i++) { // 讀取 n 行資料
for(int j=0, d; j<m; j++) { // 讀取 m 個點
cin >> d; graph[i][j] = d;
if (d < now) { // 如果 d < now
now = d; // 更新 now
sr = i; sc = j; // 更新起點座標
}
}
}
vector<pair<int, int>> que = {make_pair(sr, sc)}; // 待走訪節點
int head = 0, total = 0; // 從 que 讀取資料的索引值，加總
vector<vector<bool>> visit (n, vector<bool> (m, false)); // 走訪狀態
/* BFS */
int dr[4] = {0, -1, 0, 1}, dc[4] = {1, 0, -1, 0}; // 四方向檢測用的陣列
while(head < (int)que.size()) { // 如果 head 還沒有出界繼續執行
int r = que[head].first, c = que[head].second; head++; // 從 que 讀取座標 (r, c)，head 加 1
visit[r][c] = true; // 已走訪 (r, c)
total += graph[r][c]; // 更新 total
int imin = 10000000; // 暫存最小值的變數
for(int i=0; i<4; i++) { // 四方向檢測
int nr = r + dr[i], nc = c + dc[i]; // 要測試的座標 (nr, nc)
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue; // 如果 (nr, nc) 已出界，檢測下一個點
if (visit[nr][nc]) continue; // 如果 (nr, nc) 已走訪，檢測下一個點
if (graph[nr][nc] < imin) { // 如果 (nr, nc) 的值小於 imin
if (imin == 10000000) que.push_back(make_pair(nr, nc)); // 如果 imin 等於 10000000，找到四方向中第一個值，[nr, nc] 加入 que
else que.back() = make_pair(nr, nc); // 否則取代 que 最後一項
imin = graph[nr][nc]; // 更新 imin
}
}
}
cout << total << "\n"; // 印出答案
return 0;
}
```
<br />
### 寫法3，BFS，使用 qeque 儲存待走訪節點
於 ZeroJudge 測試結果，最長運算時間約為 13 ms，使用記憶體最多約為 338 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m; // 地圖維度 n*m
vector<vector<int>> graph (n, vector<int> (m, 0)); // 地圖
int now = 10000000, sr = 0, sc = 0; // 目前的最小值，預設為大於題目範圍的值；起點，預設為 (0, 0)
for(int i=0; i<n; i++) { // 讀取 n 行資料
for(int j=0, d; j<m; j++) { // 讀取 m 個點
cin >> d; graph[i][j] = d;
if (d < now) { // 如果 d < now
now = d; // 更新 now
sr = i; sc = j; // 更新起點座標
}
}
}
queue<pair<int, int>> que; que.push(make_pair(sr, sc)); // 待走訪節點
int total = 0; // 加總
vector<vector<bool>> visit (n, vector<bool> (m, false)); // 走訪狀態
/* BFS */
int dr[4] = {0, -1, 0, 1}, dc[4] = {1, 0, -1, 0}; // 四方向檢測用的陣列
while(!que.empty()) { // 如果 que 還有資料繼續執行
int r = que.front().first, c = que.front().second; que.pop(); // 從 que 最前面讀取並移除資料
visit[r][c] = true; // 已走訪 (r, c)
total += graph[r][c]; // 更新 total
int imin = 10000000; // 暫存最小值的變數
for(int i=0; i<4; i++) { // 四方向檢測
int nr = r + dr[i], nc = c + dc[i]; // 要測試的座標 (nr, nc)
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue; // 如果 (nr, nc) 已出界，檢測下一個點
if (visit[nr][nc]) continue; // 如果 (nr, nc) 已走訪，檢測下一個點
if (graph[nr][nc] < imin) { // 如果 (nr, nc) 的值小於 imin
if (imin == 10000000) que.push(make_pair(nr, nc)); // 如果 imin 等於 10000000，找到四方向中第一個值，[nr, nc] 加入 que
else que.back() = make_pair(nr, nc); // 否則取代 que 最後一項
imin = graph[nr][nc]; // 更新 imin
}
}
}
cout << total << "\n"; // 印出答案
return 0;
}
```
<br /><br />
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet