日期：2026年10月23日
ZeroJudge 題目連結：p920.塗鴉連線 (Doodle)
題目 pdf 檔連結：塗鴉連線 (Doodle)
解題想法
每組測資第一列為兩個整數 $m$、$n$，代表地圖尺寸為 $m \times n$，接下來 $m$ 列每列有 $n$ 個數字，$1$ 代表這格有塗黑，$0$ 代表這格沒有塗黑。起點為左上角 $(0, 0)$，終點為右下角 $(m-1, n-1)$，這兩格都是 $1$，而且只與另一格 $1$ 相鄰；起點、終點路徑上其它的 $1$ 則會與另外 $2$ 格 $1$ 相鄰。計算從起點到終點移動的格子數量。
我習慣用 BFS 處理這類型走格子的題目，但是這題並不需要用到 BFS，因為起點、終點路徑上其它的 $1$ 則會與另外 $2$ 格 $1$ 相鄰，假設已經走過的格子被標記為 $0$，用四方位檢查找出與這格相鄰的 $1$ 時只會找到 $1$ 格，只要找到這格就可以再往下走。
Python 程式碼
使用時間約為 16 ms，記憶體約為 10 MB，通過測試。
def solve():
import sys
from collections import deque
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
# 讀取測資
m = int(data[ptr])
n = int(data[ptr + 1])
ptr += 2
grid = []
for _ in range(m):
row = list(map(int, data[ptr : ptr + n]))
ptr += n
grid.append(row)
# 用 BFS 找步數
que = deque([(0, 0, 1)]) # 起點 (0, 0)，步數 1
grid[0][0] = 0 # 改成 0，標記為已走過
while que:
r, c, s = que.popleft()
if r == m - 1 and c == n - 1: # 走到終點
result.append(f"{s:d}\n")
break
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 0
que.append((nr, nc, s + 1))
# 一次輸出所有答案
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
改用 input() 讀取測資，只能通過 90% 的測資，測資 #3 的格式應該有問題。
from collections import deque
while True:
try:
m, n = map(int, input().split())
except EOFError:
break
grid = [list(map(int, input().split())) for _ in range(m)]
# 用 BFS 找步數
que = deque([(0, 0, 1)]) # 起點 (0, 0)，步數 1
grid[0][0] = 0 # 改成 0，標記為已走過
while que:
r, c, s = que.popleft()
if r == m - 1 and c == n - 1: # 走到終點
print(s)
break
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 0
que.append((nr, nc, s + 1))
使用時間約為 17 ms，記憶體約為 10 MB，通過測試。
def solve():
import sys
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
# 讀取測資
m = int(data[ptr])
n = int(data[ptr + 1])
ptr += 2
grid = []
for _ in range(m):
row = list(map(int, data[ptr : ptr + n]))
ptr += n
grid.append(row)
# 用 while loop 找步數
r, c, s = 0, 0, 1 # 起點 (0, 0)，步數 1
grid[0][0] = 0 # 改成 0，標記為已走過
while r != m - 1 or c != n - 1:
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 0
r, c = nr, nc
s += 1
break
result.append(f"{s:d}\n")
# 一次輸出所有答案
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
C++ 程式碼
使用時間約為 2 ms，記憶體約為 3.6 MB，通過測試。
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int m, n;
while(cin >> m >> n) {
// 讀取測資
vector<vector<int>> grid (m, vector<int> (n, 0));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
cin >> grid[i][j];
}
}
// 用 BFS 找步數
queue<tuple<int, int, int>> que; // 待走訪佇列
que.push({0, 0, 1}); // 起點 (0, 0)，步數 1
grid[0][0] = 0; // 改成 0，標記為已走過
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
while(!que.empty()) {
auto [r, c, s] = que.front(); // 結構化解綁定，C++ 17 的寫法
que.pop();
if (r == m - 1 && c == n - 1) { // 走到終點
cout << s << "\n";
break;
}
for(int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 0;
que.push({nr, nc, s + 1});
}
}
}
}
return 0;
}
使用時間約為 1 ms，記憶體約為 3.6 MB，通過測試。
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int m, n;
while(cin >> m >> n) {
// 讀取測資
vector<vector<int>> grid (m, vector<int> (n, 0));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
cin >> grid[i][j];
}
}
// 用 while 迴圈 找步數
int r = 0, c = 0, s = 1; // 起點 (0, 0)，步數 1
grid[0][0] = 0; // 改成 0，標記為已走過
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
while(r != m - 1 || c != n - 1) {
for(int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 0;
r = nr; c = nc; s++;
break;
}
}
}
cout << s << "\n";
}
return 0;
}
C 語言程式碼
使用時間約為 1 ms，記憶體約為 1.6 MB，通過測試。
#include <stdio.h>
typedef struct {
int r, c, s;
} Pos;
int main() {
int m, n;
while(scanf("%d %d", &m, &n) != EOF) {
// 讀取測資
int grid[20][20];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &grid[i][j]);
}
}
// 用 BFS 找步數
int head = 0, total = 1;
Pos que[400]; // 待走訪佇列
que[0].r = 0; que[0].c = 0; que[0].s = 1; // 起點 (0, 0)，步數 1
grid[0][0] = 0; // 改成 0，標記為已走過
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
while(head < total) {
int r = que[head].r, c = que[head].c, s = que[head].s;
head++;
if (r == m - 1 && c == n - 1) { // 走到終點
printf("%d\n", s);
break;
}
for(int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 0;
que[total].r = nr; que[head].c = nc; que[head].s = s + 1;
total++;
}
}
}
}
return 0;
}
使用時間約為 1 ms，記憶體約為 1.6 MB，通過測試。
#include <stdio.h>
int main() {
int m, n;
while(scanf("%d %d", &m, &n) != EOF) {
// 讀取測資
int grid[20][20];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &grid[i][j]);
}
}
// 用 while 迴圈找步數
int r = 0, c = 0, s = 1;
grid[0][0] = 0; // 改成 0，標記為已走過
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
while(r != m - 1 || c != n - 1) {
for(int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 0;
r = nr; c = nc; s++;
break;
}
}
}
printf("%d\n", s);
}
return 0;
}
沒有留言:
張貼留言