HDU 5652 India and China Origins：動態阻隔下的連通性判斷

問題描述

給定 N×M 網格，初始有山地（1）與平地（0）。起點為頂行任意平地，終點為底行任意平地。每年在指定坐標生成一座新山（不可通行）。求通訊完全中斷的最早年份，若始終連通輸出 -1。

解題策略：逆向思維 + 並查集

正向模擬每年增加障礙物並檢查連通性代價高。改用離線逆向處理：

1. 將所有 Q 年的山全部標記為阻隔，構建最終地圖。
2. 從最終狀態開始，反向逐年「移除」山（即恢復平地），維護頂底行連通性。
3. 首次出現頂底行連通時，對應的年份即為答案（正向即該年斷開）。

並查集維護連通分量，虛擬節點 S 連接頂行所有平地，T 連接底行所有平地。若 find(S) == find(T) 則連通。

關鍵步驟

• 初始化：讀入地圖，標記所有將生成的山為阻隔。
• 構建初始並查集：遍歷所有平地，合併相鄰平地；頂/底行平地分別連 S/T。
• 逆向處理：從第 Q 年倒至第 1 年，將該年山點恢復為平地，合併其四鄰域平地，檢查 S、T 是否連通。
• 輸出：首次連通的年份（正向即斷開年份）；若循環結束仍不連通，輸出 -1。

複雜度

時間 O(NM α(NM) + Q α(NM))，空間 O(NM)，滿足 N,M ≤ 500 限制。