#38781: 較簡短寫法 - 解題思路(含一些小技巧)


edoctopus322@gmail.com (Moon Jam)

School : 臺北市立成功高級中學
ID : 167591
IP address : [36.225.19.60]
Last Login :
2023-12-23 13:47:18
g596. 2. 動線安排 -- 2021年11月APCS | From: [36.225.19.60] | Post Date : 2023-12-23 13:25

完整題解:https://moon-jam.me/zerojudge_g596/

解題思路:
狀態
每個格子存在的5種狀況(空的、木樁、直線、橫線、交線)用五個數字表示:0、1、2、3、5(交線用5是因為後面實作連線和拔線的時候,可以直接用加或減,讓一條線的狀態轉移到交線,或將交線的狀態轉移到一條線)
 
遍歷整張圖的每個格子,若該格子的狀態不為0,則將面積加一(因為最後要輸出過程中最大面積,因此我多開一個變數max_cnt紀錄)
 
拔木樁
先把該點木樁拔掉(設為0),再往四個方向找線,如果有線就將跟目前前進方向相同的線拔掉(假設目前是往上找,如果確認這個點是線,那就將那個點的狀態減2,因此該點是直線會變0(空的),交線則變3(橫線))
 
建木樁
先將指定點的狀態設為1,接著往四個方向找木樁,如果確認有木樁就建線,建線的作法跟拔線相似(假設目前是往上找,如果目前點的狀態是2(直線)或0(空的)那就設成2,如果狀態是3(橫線)就設成5(交線),而如果狀態是5就不改變)
 
主程式
有前面那些函式後就簡單了,讀輸入然後呼叫建木樁或拔木樁,最後再輸出答案就完成了
 
🌟 要注意的是線有分成直向和橫向,直的被刪掉之後橫的不會被刪掉,若一個格子內同時存在直線和橫線,在刪掉其中一個的時候,另一個方向的線還要繼續存在,另外就是新的木樁放上去之後,不管原先那個格子上的線是什麼,會直接被刪掉,然後再由那個木樁往四個方向連線
 
ZeroJudge Forum