一、概念
 |
| 轉換成正規棋盤 |
此題題意為給予一個值為0或1的正方形棋盤（如上圖Original），只透過行/列交換，而轉換成正規的棋盤（如上圖Swapping）。如果可以轉換成正規棋盤，則回傳最少交換次數（含0與正整數）；而如果不可以轉換成正規棋盤，則回傳-1（代表不合法）。
- 行/列各有2種不同型態 (type)，上圖行由{0, 1, 1, 0, 1, 0}和{1, 0, 0, 1, 0, 1}所組成，而列由{0, 0, 1, 0, 1, 1}和{1, 1, 0, 1, 0, 0, 0}組成。
- 行/列交換雖會改變型態，但型態仍保持2種。
- 2種不同型態的數量差≤1，即差只會為0（當棋盤為偶數）或1（當棋盤為奇數）。
- 2種不同型態的排列最終會交差排列，可能為ans1{0, 1, 0, 1, ...}或ans2{1, 0, 1, 0, ...}
因此，我們可以先計算original行/列有幾種型態，如果型態數≠2，則不合法。此外還要確保2種不同型態的數量差≤1，如果數量差>2，也是不合法。然後給這兩型態貼標籤，分別為0和1，並計算行/列和ans1與ans2的差異。合法的差異數為偶數，不合法的差異數為奇數（只會發生在奇數棋盤），而最小差異數/2即為行/列的最小交換數。最後將行與列的最小交換數相加，即為轉換為正規棋盤的最小交換次數。
二、實作
 |
| Transform to Chessboard 主架構 |
第1步先找出行/列有幾種不同的型態 (diffRow, diffCol)，並紀錄型態 (0 or 1)的分佈於row、col陣列中。1.1和1.3執行找尋與紀錄的工作；1.2則是將board轉置為tBoard，雖然轉置很花運算，但可以重複利用findRowDiff()；1.4則是檢查其row和col的合法性。第2步分別計算出row和col最小交換次數，並加總回傳。
 |
| findRowDiff() 程式碼 |
我們會有diffRow紀錄列的不同型態，以及row紀錄列的型態分佈。第1列會預設為第一個型態，並依序檢查第2~n列是否有新的型態，如果有新型態 (d<1)則加入diffRow中，如果型態數>2 (d>1)，則回傳-1代表不合法。
 |
| isValid() 程式碼 |
 |
| isRowSame()和minSwap() 程式碼 |
如果0/1數量皆為偶數，則不會有非法解的問題；但如果0/1數量其中一個為奇數，則會有非法解的問題。因此可以先計算0/1的奇偶性，再開始與ans1或ans2做比較。如果0為奇數，則ans1為合法，如果1為奇數，則ans2為合法。
三、改善
（ㄧ）位元運算 (bit expression)
上述上為了簡化與提高可讀性，而犧牲一些速度的部分（轉置）。在實作架構上可以改成位元運算 (bit expression)，以加速整體的速度。因為輸入的board值必為0/1，且合法的型態只有2種，故可利用XOR (Exclusive-OR gate)去實作isRowSame()和findRowDiff()。如果相同，XOR會給予False；如果不相同XOR會給予True，此性質可判別異同。
（二）ans1和ans2彼此互補
minSwap()可以再減少計算，因為ans1和ans2彼此互補，因此ans1 + ans2 = size。故其實只要計算出ans1，就可以透過size反推出ans2。
留言
張貼留言