APCS實作題2022年6月第3題：雷射測試

# APCS實作題2022年6月第3題：雷射測試 > 日期：2024年8月8日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=i401) ## 題目 ### 問題描述一個雷射光從 $(0,0)$ 向右邊發射，平面上有很多個鏡子，問雷射光會反射幾次，保證輸入沒有無限循環的情形。鏡子用三個數字表示 $(x_i, y_i, t_i)$，代表座標在 $(x_i, y_i)$ 上。$t_i = 0$ 代表示這種 / 擺放方式的鏡子，$t_i = 1$ 代表這種 \ 擺放方式的鏡子，保證不會有一個位置有多個鏡子。 <img style="display: block; margin-left: auto; margin-right: auto" height="40%" width="40%" src="https://i.imgur.com/cIaeuCg.png"> <div style="text-align:center">輸入範例1圖示</div> ### 輸入說明輸入一個正整數 $n ~(1 \leq n \leq 250000)$，代表鏡子的數量，接下來有 $n$ 行，第 $i$ 行有三個數字 $x_i$、$y_i$ 和 $t_i$。子題配分 - 20%：$1 \leq n \leq 1000,~ 1 \leq x_i \leq 100,~ -100 \leq y_i \leq 100$ - 80%：$1 \leq n \leq 250000,~ 1 \leq x_i \leq 30000,~ -30000 \leq y_i \leq 30000$ ### 輸出格式輸出雷射光共反射幾次。 ### 範例輸入1 ``` 10 2 0 1 2 -1 1 7 -1 0 7 2 1 4 2 0 4 1 0 3 1 1 3 2 0 1 -1 1 1 4 0 ``` ### 範例輸出1 ``` 9 ``` ### 範例輸入2 ``` 4 2 1 0 5 -3 1 4 2 1 6 -2 0 ``` ### 範例輸出2 ``` 0 ``` ## Python 程式碼用字典儲存排序後的鏡子資料，再用二分搜尋法找下一面鏡子，如果沒有找到符合規則的鏡子就中止迴圈，印出答案。沒有用到比較進階的語法或資料結構，花費時間較長，使用比較多的記憶體，但是程式碼比較好懂。費時最久約為 1.9 s，使用記憶體最多約為 46.4 MB，通過測試。 ```python= from bisect import bisect_left # 引入二分搜尋法函式庫 n = int(input()) # 鏡子數量 xs = dict() # 在指定的 x 座標上的鏡子資料，內容為 [(yi, ti)] ys = dict() # 在指定的 y 座標上的鏡子資料，內容為 [(xi, ti)] for _ in range(n): # 讀取 n 行資料 xi, yi, ti = map(int, input().split()) # 讀取 xi, yi, ti if xi not in xs: xs[xi] = [(yi, ti)] # 如果 xi 不在 xs 之中，新增 xi 對應的資料，串列中只有一組 (yi, ti) else: xs[xi].append((yi, ti)) # 如果 xi 已經在 xs 之中，xi 對應的資料再加上一組 (yi, ti) if yi not in ys: ys[yi] = [(xi, ti)] # 如果 yi 不在 ys 之中，新增 yi 對應的資料，串列中只有一組 (xi, ti) else: ys[yi].append((xi, ti)) # 如果 yi 已經在 ys 之中，yi 對應的資料再加上一組 (xi, ti) for y in xs.values(): y.sort() # 依序取出 xs 中的資料，由小到大排序 for x in ys.values(): x.sort() # 依序取出 ys 中的資料，由小到大排序 dirs = ((1, 3), (0, 2), (3, 1), (2, 0)) # 原來的方向對應的反射後方向，0右，1上，2左，3下 d = 0 # 目前的方向，預設為0右 ans = 0 # 答案，反射次數 xc, yc = 0, 0 # 目前的位置 xn, yn, tn = 0, 0, 0 # 下一個位置，找到的鏡子種類 while True: if d == 0: # 向右 if yc not in ys: break # 如果 y = yc 上沒有鏡子，中止迴圈 else: idx = bisect_left(ys[yc], (xc+1, -1)) # 找 y = yc 這行 x > xc 的鏡子 #print("d = 0, idx = ", idx) if idx == len(ys[yc]): break # 沒有找到鏡子，中止迴圈 if ys[yc][idx][0] == xc: idx += 1 # 如果找到現在的鏡子，idx 加 1 if idx < len(ys[yc]): # 如果 idx 沒有出界，找到符合規則的鏡子 ans += 1 # 答案加 1 xn, tn = ys[yc][idx] # 更新 xn, tn yn = yc # 更新 yn else: break # 如果 idx 出界，中止迴圈 elif d == 2: # 向左 if yc not in ys: break # 如果 y = yc 上沒有鏡子，中止迴圈 else: idx = bisect_left(ys[yc], (xc-1, -1)) # 找 y = yc 這行 x < xc 的鏡子 #print("d = 2, idx = ", idx) if idx == len(ys[yc]): break # 沒有找到鏡子，中止迴圈 if ys[yc][idx][0] == xc: idx -= 1 # 如果找到現在的鏡子，idx 減 1 if idx >= 0: # 如果 idx 沒有出界，找到符合規則的鏡子 ans += 1 # 答案加 1 xn, tn = ys[yc][idx] # 更新 xn, tn yn = yc # 更新 yn else: break # 如果 idx 出界，中止迴圈 elif d == 1: # 向上 if xc not in xs: break # 如果 x = xc 上沒有鏡子，中止迴圈 else: idx = bisect_left(xs[xc], (yc+1, -1)) # 找 x = xc 這行 y > yc 的鏡子 #print("d = 1, idx = ", idx) if idx == len(xs[xc]): break # 沒有找到鏡子，中止迴圈 if xs[xc][idx][0] == yc: idx += 1 # 如果找到現在的鏡子，idx 加 1 if idx < len(xs[xc]): # 如果 idx 沒有出界，找到符合規則的鏡子 ans += 1 # 答案加 1 yn, tn = xs[xc][idx] # 更新 yn, tn xn = xc # 更新 xn else: break # 如果 idx 出界，中止迴圈 elif d == 3: # 向下 if xc not in xs: break # 如果 x = xc 上沒有鏡子，中止迴圈 else: idx = bisect_left(xs[xc], (yc-1, -1)) # 找 x = xc 這行 y < yc 的鏡子 #print("d = 3, idx = ", idx) if idx == len(xs[xc]): break # 沒有找到鏡子，中止迴圈 if xs[xc][idx][0] == yc: idx -= 1 # 如果找到現在的鏡子，idx 減 1 if idx >= 0: # 如果 idx 沒有出界，找到符合規則的鏡子 ans += 1 # 答案加 1 yn, tn = xs[xc][idx] # 更新 yn, tn xn = xc # 更新 xn else: break # 如果 idx 出界，中止迴圈 d = dirs[d][tn] # 更新方向 xc, yc = xn, yn # 更新 xc, yc #print(xn, yn, tn, d, ans) print(ans) ``` ## C++ 程式碼以下的程式碼中有幾個需要注意的細節。 1. 第18、19行，要用迭代器取出指定記憶體位址的資料，使用 sort 將資料排序後才能改變字典中原來的資料順序。 2. 第31、44、57、70行，使用 lower_bound 找指定的 pair 時，要先用 make_pair 將數對組成 pair，不能直接用 {} 包起來。費時最久約為 0.2 s，使用記憶體最多約為 9.2 MB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <map> #include <utility> // for pair #include <algorithm> // for lower_bound using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); // 加速 int n; cin >> n; // 鏡子數量 // xs 在指定的 x 座標上的鏡子資料，內容為 [(yi, ti)]。 ys 在指定的 y 座標上的鏡子資料，內容為 [(xi, ti)] map<int, vector<pair<int, int>>> xs, ys; for(int i=0; i<n; i++) { // 讀取 n 行資料 int xi, yi, ti; cin >> xi >> yi >> ti; // 讀取 xi, yi, ti xs[xi].push_back({yi, ti}); // xi 對應的資料再加上一組 (yi, ti) ys[yi].push_back({xi, ti}); // yi 對應的資料再加上一組 (xi, ti) } for(auto it = xs.begin(); it != xs.end(); it++) sort((*it).second.begin(), (*it).second.end()); // 依序取出 xs 中的資料，由小到大排序 for(auto it = ys.begin(); it != ys.end(); it++) sort((*it).second.begin(), (*it).second.end()); // 依序取出 ys 中的資料，由小到大排序 int dirs[4][2] = {{1, 3}, {0, 2}, {3, 1}, {2, 0}}; // 原來的方向對應的反射後方向，0右，1上，2左，3下 int d = 0; // 目前的方向，預設為0右 int ans = 0; // 答案，反射次數 int xc = 0, yc = 0; // 目前的位置 int xn = 0, yn = 0, tn = 0; // 下一個位置，找到的鏡子種類 while(true) { if (d == 0) { // 向右 if (ys[yc].empty()) break; // 如果 y = yc 上沒有鏡子，中止迴圈 else { int idx = lower_bound(ys[yc].begin(), ys[yc].end(), make_pair(xc+1, -1)) - ys[yc].begin(); // 找 y = yc 這行 x > xc 的鏡子 //cout << "d = 0, idx = " << idx << "\n"; if (idx == (int)ys[yc].size()) break; // 沒有找到鏡子，中止迴圈 if (ys[yc][idx].first == xc) idx++; // 如果找到現在的鏡子，idx 加 1 if (idx < (int)ys[yc].size()) { // 如果 idx 沒有出界，找到符合規則的鏡子 ans++; // 答案加 1 xn = ys[yc][idx].first; tn = ys[yc][idx].second; // 更新 xn, tn yn = yc; // 更新 yn } else break; // 如果 idx 出界，中止迴圈 } } else if (d == 2) { // 向左 if (ys[yc].empty()) break; // 如果 y = yc 上沒有鏡子，中止迴圈 else { int idx = lower_bound(ys[yc].begin(), ys[yc].end(), make_pair(xc-1, -1)) - ys[yc].begin(); // 找 y = yc 這行 x < xc 的鏡子 //cout << "d = 2, idx = " << idx << "\n"; if (idx == (int)ys[yc].size()) break; // 沒有找到鏡子，中止迴圈 if (ys[yc][idx].first == xc) idx--; // 如果找到現在的鏡子，idx 減 1 if (idx >= 0) { // 如果 idx 沒有出界，找到符合規則的鏡子 ans++; // 答案加 1 xn = ys[yc][idx].first; tn = ys[yc][idx].second; // 更新 xn, tn yn = yc; // 更新 yn } else break; // 如果 idx 出界，中止迴圈 } } else if (d == 1) { // 向上 if (xs[xc].empty()) break; // 如果 x = xc 上沒有鏡子，中止迴圈 else { int idx = lower_bound(xs[xc].begin(), xs[xc].end(), make_pair(yc+1, -1)) - xs[xc].begin(); // 找 x = xc 這行 y > yc 的鏡子 //cout << "d = 1, idx = " << idx << "\n"; if (idx == (int)xs[xc].size()) break; // 沒有找到鏡子，中止迴圈 if (xs[xc][idx].first == yc) idx++; // 如果找到現在的鏡子，idx 加 1 if (idx < (int)xs[xc].size()) { // 如果 idx 沒有出界，找到符合規則的鏡子 ans++; // 答案加 1 yn = xs[xc][idx].first; tn = xs[xc][idx].second; // 更新 yn, tn xn = xc; // 更新 xn } else break; // 如果 idx 出界，中止迴圈 } } else if (d == 3) { // 向下 if (xs[xc].empty()) break; // 如果 x = xc 上沒有鏡子，中止迴圈 else { int idx = lower_bound(xs[xc].begin(), xs[xc].end(), make_pair(yc-1, -1)) - xs[xc].begin(); // 找 x = xc 這行 y < yc 的鏡子 //cout << "d = 3, idx = " << idx << "\n"; if (idx == (int)xs[xc].size()) break; // 沒有找到鏡子，中止迴圈 if (xs[xc][idx].first == yc) idx--; // 如果找到現在的鏡子，idx 減 1 if (idx >= 0) { // 如果 idx 沒有出界，找到符合規則的鏡子 ans++; // 答案加 1 yn = xs[xc][idx].first; tn = xs[xc][idx].second; // 更新 yn, tn xn = xc; // 更新 xn } else break; // 如果 idx 出界，中止迴圈 } } d = dirs[d][tn]; // 更新方向 xc = xn; yc = yn; // 更新 xc, yc //cout << "xn: " << xn << "yn: " << yn << "tn: " << tn << "d: " << d << "ans: " << ans << "\n"; } cout << ans << "\n"; return 0; } ``` --- ###### tags:`APCS`、`Python`、`C++`