日期：2025年9月7日
ZeroJudge 題目連結：d626. 小畫家真好用
解題想法
用 BFS 及四方位檢查解題，由於我比較懶得檢查邊界值，我會在周圍加上 + 當作哨兵避免出界。
Python 程式碼
使用時間約為 24 ms，記憶體約為 3.5 MB，通過測試。
n = int(input()) # 地圖 n*n
grid = [list(input().strip()) + ["+"] for _ in range(n)] # 讀取地圖資料，最右側加上 + 作為哨兵
grid.append(list("+"*(n+1))) # 最下方加 n+1 個 + 作為哨兵
que = [tuple(map(int, input().split()))] # 待走訪佇列，先放入起點
head = 0 # 從 que 讀取資料用的索引值
while head < len(que): # BFS，當 head 還沒有出界繼續執行
r, c = que[head]; head += 1 # 從 que 讀取要走訪的點 (r, c)，head 加 1
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)): # 四方位檢查
nr, nc = r+dr, c+dc # 要檢查的點 (nr, nc)
if grid[nr][nc] == "+": continue # 如果 grid[nr][nc] 是 +，找下一個點
grid[nr][nc] = "+" # grid[nr][nc] 改成 +
que.append((nr, nc)) # (nr, nc) 加入 que
for i in range(n): print("".join(grid[i][:n])) # 依序讀取 grid[:n][:n]，接成字串再輸出
改用 deque 儲存待走訪節點，使用時間約為 25 ms，記憶體約為 3.7 MB，通過測試。
from collections import deque
n = int(input()) # 地圖 n*n
grid = [list(input().strip()) + ["+"] for _ in range(n)] # 讀取地圖資料，最右側加上 + 作為哨兵
grid.append(list("+"*(n+1))) # 最下方加 n+1 個 + 作為哨兵
que = deque([tuple(map(int, input().split()))]) # 待走訪佇列，先放入起點
while que: # BFS，當 que 還有資料繼續執行
r, c = que.popleft() # 從 que 開頭讀取並移除要走訪的點 (r, c)
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)): # 四方位檢查
nr, nc = r+dr, c+dc # 要檢查的點 (nr, nc)
if grid[nr][nc] == "+": continue # 如果 grid[nr][nc] 是 +，找下一個點
grid[nr][nc] = "+" # grid[nr][nc] 改成 +
que.append((nr, nc)) # (nr, nc) 加入 que
for i in range(n): print("".join(grid[i][:n])) # 依序讀取 grid[:n][:n]，接成字串再輸出
C++ 程式碼
寫法1，用字串陣列儲存地圖，用 vector 儲存待走訪的點，使用時間約為 2 ms，記憶體約為 368 kB，通過測試。
#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;
int main () {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n; // 地圖 n*n
vector<string> grid (n+2); // 地圖資料，四周加上一圈 + 作為哨兵
string s (n+2, '+'); // n+2 個 +
grid[0] = s; grid[n+1] = s; // 處理 grid[0], grid[n+1]
for(int i=1; i<=n; i++) { // 處理 grid[1] ~ grid[n]
cin >> s; grid[i] = '+' + s + '+';
}
vector<pair<int, int>> que (1); // 待走訪佇列，先放入起點
cin >> que[0].first >> que[0].second;
que[0].first++; que[0].second++; // 座標要加 1
int head = 0; // 從 que 讀取資料用的索引值
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查用的位移量
while(head < (int)que.size()) { // BFS，當 head 還沒有出界繼續執行
int r = que[head].first, c = que[head].second; head++; // 從 que 讀取要走訪的點 (r, c)，head 加 1
for(int i=0; i<4; i++) { // 四方位檢查
int nr = r+dr[i], nc = c+dc[i]; // 要檢查的點 (nr, nc)
if (grid[nr][nc] == '+') continue; // 如果 grid[nr][nc] 是 +，找下一個點
grid[nr][nc] = '+'; // grid[nr][nc] 改成 +
que.push_back(make_pair(nr, nc)); // (nr, nc) 加入 que
}
}
for(int i=1; i<=n; i++) cout << grid[i].substr(1, n) << "\n"; // 印出不包含哨兵的地圖
return 0;
}
寫法2，用字串陣列儲存地圖，用 queue 儲存待走訪的點，使用時間約為 2 ms，記憶體約為 356 kB，通過測試。
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
int main () {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n; // 地圖 n*n
vector<string> grid (n+2); // 地圖資料，四周加上一圈 + 作為哨兵
string s (n+2, '+'); // n+2 個 +
grid[0] = s; grid[n+1] = s; // 處理 grid[0], grid[n+1]
for(int i=1; i<=n; i++) { // 處理 grid[1] ~ grid[n]
cin >> s; grid[i] = '+' + s + '+';
}
queue<pair<int, int>> que; // 待走訪佇列，先放入起點
int sr, sc; cin >> sr >> sc; sr++; sc++; // 座標要加 1
que.push(make_pair(sr, sc));
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查用的位移量
while(!que.empty()) { // BFS，當 que 還有資料繼續執行
int r = que.front().first, c = que.front().second; que.pop(); // 從 que 讀取要走訪的點 (r, c)，head 加 1
for(int i=0; i<4; i++) { // 四方位檢查
int nr = r+dr[i], nc = c+dc[i]; // 要檢查的點 (nr, nc)
if (grid[nr][nc] == '+') continue; // 如果 grid[nr][nc] 是 +，找下一個點
grid[nr][nc] = '+'; // grid[nr][nc] 改成 +
que.push(make_pair(nr, nc)); // (nr, nc) 加入 que
}
}
for(int i=1; i<=n; i++) cout << grid[i].substr(1, n) << "\n"; // 印出不包含哨兵的地圖
return 0;
}
寫法3，用二維字元陣列儲存地圖，用 vector 儲存待走訪的點，使用時間約為 2 ms，記憶體約為 292 kB，通過測試。
#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
int main () {
int n; scanf("%d", &n); // 地圖 n*n
char grid[n+2][n+2]; // 地圖資料，四周加上一圈 + 作為哨兵
for(int i=0; i<n+2; i++) { // 處理 grid[0], grid[n+1]
grid[0][i] = '+'; grid[n+1][i] = '+';
}
for(int i=1; i<=n; i++) { // 處理 grid[1] ~ grid[n]
scanf("%s", grid[i]+1);
grid[i][0] = '+'; grid[i][n+1] = '+';
}
vector<pair<int, int>> que (1); // 待走訪佇列，先放入起點
scanf("%d %d", &que[0].first, &que[0].second);
que[0].first++; que[0].second++; // 座標要加 1
int head = 0; // 從 que 讀取資料用的索引值
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查用的位移量
while(head < (int)que.size()) { // BFS，當 head 還沒有出界繼續執行
int r = que[head].first, c = que[head].second; head++; // 從 que 讀取要走訪的點 (r, c)，head 加 1
for(int i=0; i<4; i++) { // 四方位檢查
int nr = r+dr[i], nc = c+dc[i]; // 要檢查的點 (nr, nc)
if (grid[nr][nc] == '+') continue; // 如果 grid[nr][nc] 是 +，找下一個點
grid[nr][nc] = '+'; // grid[nr][nc] 改成 +
que.push_back(make_pair(nr, nc)); // (nr, nc) 加入 que
}
}
for(int i=1; i<=n; i++) { // 印出不包含哨兵的地圖
for(int j=1; j<=n; j++) printf("%c", grid[i][j]);
puts("");
}
return 0;
}
寫法4，用二維字元陣列儲存地圖，用 queue 儲存待走訪的點，使用時間約為 3 ms，記憶體約為 280 kB，通過測試。
#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
int main () {
int n; scanf("%d", &n); // 地圖 n*n
char grid[n+2][n+2]; // 地圖資料，四周加上一圈 + 作為哨兵
for(int i=0; i<n+2; i++) { // 處理 grid[0], grid[n+1]
grid[0][i] = '+'; grid[n+1][i] = '+';
}
for(int i=1; i<=n; i++) { // 處理 grid[1] ~ grid[n]
scanf("%s", grid[i]+1);
grid[i][0] = '+'; grid[i][n+1] = '+';
}
queue<pair<int, int>> que; // 待走訪佇列，先放入起點
int sr, sc; scanf("%d %d", &sr, &sc);
sr++; sc++; // 座標要加 1
que.push(make_pair(sr, sc));
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查用的位移量
while(!que.empty()) { // BFS，當 que 還有資料繼續執行
int r = que.front().first, c = que.front().second; que.pop(); // 從 que 讀取要走訪的點 (r, c)，head 加 1
for(int i=0; i<4; i++) { // 四方位檢查
int nr = r+dr[i], nc = c+dc[i]; // 要檢查的點 (nr, nc)
if (grid[nr][nc] == '+') continue; // 如果 grid[nr][nc] 是 +，找下一個點
grid[nr][nc] = '+'; // grid[nr][nc] 改成 +
que.push(make_pair(nr, nc)); // (nr, nc) 加入 que
}
}
for(int i=1; i<=n; i++) { // 印出不包含哨兵的地圖
for(int j=1; j<=n; j++) printf("%c", grid[i][j]);
puts("");
}
return 0;
}
沒有留言:
張貼留言