日期：2025年5月17日
ZeroJudge 題目連結：k930. P7. 興建圍籬 (Fence)
解題想法
這題我用 BFS，但是在 Python 不論是用 deque 或 list 都太慢，在 C++ 用 queue 或 vector 都要跑 0.1 s。
Python 程式碼
寫法1，用 deque 儲存待走訪的佇列，但是速度不夠快，只能通過 60% 的測資。
import sys
from collections import deque
for line in sys.stdin:
H, W = map(int, line.split()) # 地圖 H*W
grid = [list(map(int, input().split())) for _ in range(H)] # 讀取地圖
num = 1 # 花地編號
ans = [] # 答案
for i in range(H): # 依序掃過每一格
for j in range(W):
if grid[i][j] == 1: # 如果此格是花地
tot = 0 # 這區的圍籬數量
que = deque([(i, j)]) # 待走訪的佇列
num += 1 # 編號加 1
while que: # 如果 que 還有資料繼續執行
r, c = que.popleft() # 從 que 開頭讀取並移除資料
grid[r][c] = num # 設定 grid[r][c] 的編號
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)): # 四方位檢查
nr, nc = r+dr, c+dc # 要檢查的格子 (nr, nc)
if 0 <= nr < H and 0 <= nc < W: # 如果 nr, nc 沒有出界
if grid[nr][nc] == 1: # 如果是還沒有編號的花地
grid[nr][nc] = num # 設定編號
que.append((nr, nc)) # (nr, nc) 加入 que
elif grid[nr][nc] == 0: # 如果是空地
tot += 1 # (r, c) 需要加一片圍籬
ans.append(tot) # 將 tot 加入 ans
print(*sorted(ans)) # 將 ans 排序後印出
寫法2，用串列儲存待走訪的佇列，但是速度不夠快，只能通過 60% 的測資。
import sys
for line in sys.stdin:
H, W = map(int, line.split()) # 地圖 H*W
grid = [list(map(int, input().split())) for _ in range(H)] # 讀取地圖
num = 1 # 花地編號
ans = [] # 答案
for i in range(H): # 依序掃過每一格
for j in range(W):
if grid[i][j] == 1: # 如果此格是花地
tot = 0 # 這區的圍籬數量
que = [(i, j)] # 待走訪的佇列
head = 0 # 從 que 讀取資料的索引值
num += 1 # 編號加 1
while head < len(que): # 如果 head 還沒有出界繼續執行
r, c = que[head]; head += 1 # 從 que 讀取位置，head 加 1
grid[r][c] = num # 設定 grid[r][c] 的編號
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)): # 四方位檢查
nr, nc = r+dr, c+dc # 要檢查的格子 (nr, nc)
if 0 <= nr < H and 0 <= nc < W: # 如果 nr, nc 沒有出界
if grid[nr][nc] == 1: # 如果是還沒有編號的花地
grid[nr][nc] = num # 設定編號
que.append((nr, nc)) # (nr, nc) 加入 que
elif grid[nr][nc] == 0: # 如果是空地
tot += 1 # (r, c) 需要加一片圍籬
ans.append(tot) # 將 tot 加入 ans
print(*sorted(ans)) # 將 ans 排序後印出
C++ 程式碼
寫法1，用 queue 儲存待走訪的佇列，使用時間約為 0.1 s，記憶體約為 4.9 MB，通過測試。
#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查用的位移量
int H, W; // 地圖 H*W
while(scanf("%d %d", &H, &W) != EOF) {
int grid[H][W]; // 讀取地圖
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
scanf("%d", &grid[i][j]);
}
}
int num = 1; // 花地編號
vector<int> ans; // 答案
for(int i=0; i<H; i++) { // 依序掃過每一格
for(int j=0; j<W; j++) {
if (grid[i][j] == 1) { // 如果此格是花地
int tot = 0; // 這區的圍籬數量
queue<pair<int, int>> que; que.push(make_pair(i, j)); // 待走訪的佇列
num++; // 編號加 1
while(!que.empty()) { // 如果 que 還有資料繼續執行
int r = que.front().first, c = que.front().second; // 從 que 開頭讀取位置
que.pop(); // 移除 que 開頭的資料
grid[r][c] = num; // 設定 grid[r][c] 的編號
for(int k=0; k<4; k++) { // 四方位檢查
int nr = r+dr[k], nc = c+dc[k]; // 要檢查的格子 (nr, nc)
if (nr >= 0 && nr < H && nc >= 0 && nc < W) { // 如果 nr, nc 沒有出界
if (grid[nr][nc] == 1) { // 如果是還沒有編號的花地
grid[nr][nc] = num; // 設定編號
que.push(make_pair(nr, nc)); // (nr, nc) 加入 que
} else if (grid[nr][nc] == 0) { // 如果是空地
tot++; // (r, c) 需要加一片圍籬
}
}
}
}
ans.push_back(tot); // 將 tot 加入 ans
}
}
}
sort(ans.begin(), ans.end()); // 將 ans 排序後印出
int m = (int)ans.size();
for(int i=0; i<m; i++) {
printf("%d", ans[i]);
if (i == m-1) printf("\n");
else printf(" ");
}
}
return 0;
}
寫法2，用 vector 儲存待走訪的佇列，使用時間約為 0.1 s，記憶體約為 5 MB，通過測試。
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查用的位移量
int H, W; // 地圖 H*W
while(scanf("%d %d", &H, &W) != EOF) {
int grid[H][W]; // 讀取地圖
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
scanf("%d", &grid[i][j]);
}
}
int num = 1; // 花地編號
vector<int> ans; // 答案
for(int i=0; i<H; i++) { // 依序掃過每一格
for(int j=0; j<W; j++) {
if (grid[i][j] == 1) { // 如果此格是花地
int tot = 0, head = 0; // 這區的圍籬數量，從 que 讀取資料的索引值
vector<pair<int, int>> que = {make_pair(i, j)}; // 待走訪的佇列
num++; // 編號加 1
while(head < (int)que.size()) { // 如果 head 還沒有出界繼續執行
int r = que[head].first, c = que[head].second; // 從 que 讀取位置
head++; // head 加 1
grid[r][c] = num; // 設定 grid[r][c] 的編號
for(int k=0; k<4; k++) { // 四方位檢查
int nr = r+dr[k], nc = c+dc[k]; // 要檢查的格子 (nr, nc)
if (nr >= 0 && nr < H && nc >= 0 && nc < W) { // 如果 nr, nc 沒有出界
if (grid[nr][nc] == 1) { // 如果是還沒有編號的花地
grid[nr][nc] = num; // 設定編號
que.push_back(make_pair(nr, nc)); // (nr, nc) 加入 que
} else if (grid[nr][nc] == 0) { // 如果是空地
tot++; // (r, c) 需要加一片圍籬
}
}
}
}
ans.push_back(tot); // 將 tot 加入 ans
}
}
}
sort(ans.begin(), ans.end()); // 將 ans 排序後印出
int m = (int)ans.size();
for(int i=0; i<m; i++) {
printf("%d", ans[i]);
if (i == m-1) printf("\n");
else printf(" ");
}
}
return 0;
}
沒有留言:
張貼留言