tioj 1333 番茄小豆湯

Dancing Links( Knuth實在太罩了 )


其實我從來都沒有寫過link，結果第一次就寫了dancing links


感覺起來真的超級複雜的＝＝


寫了80 行，又多又醜真是太糟糕了QQ


先講講概念再來說實作好了XD


概念：
       先討論Links, 平常人在用Links時，他是用指標來互相只來只去的一種資料結構。普通人主要是用他的快速刪除機制，而當一個程式設計師把一個點刪除時，為了安全與保險，通常會把它的left跟right都指向自己或NULL，因為他們覺得有一個外面的東西可以連進去是危險的。

L[R[x]] = L[x]; R[L[x]] = R[x];   

       但是Dancing Links實在是超級活躍的～，他用到的概念是這樣的，他反其道而行，故意讓自己的左右維持不變，這時你就可以快速的把被刪掉的東西UNDO囉！XD

L[R[x]] = x; R[L[x]] = x;

      不要以為這只是個耍耍廢的常識，這可是2000年Knuth教授發表的超強論文中的關鍵所在阿！有了基礎後就要進入應用了。這個性質（刪去用復原）感覺就非常的DFS，很有回溯的味道，他超棒的用處就在於加快暴搜速度，大概看一下這個題目（也就是所謂的精準覆蓋），你會發現他越到後面，其實有很多行列根本完全不需要去尋找，卻要一直去花那可憐的n^2，這時心中就冒出一種想法，乾脆把它刪掉吧！Dancing Links就如此的誕生了～（在Knuth的腦中XD），你就不斷的在搜尋時將他刪除刪除刪除，之後再將他補回補回補回，就可以進行回溯法了～


實作：
      有了概念後，一切都只剩下如何實作了，說到實作就快崩壞＝＝，居然寫了快100行，我會把code放在後面，但是還是不要看比較好，我直接講作法，簡單易懂。首先要討論如何去記錄，有些人會把每一個node當成是某一個只是個node的東西（存取位置不具有上下左右的，像這個），但我把它寫成陣列，接下來就是要連接每一個點了，如果是0的話，其實可以直接跳過去，不需要連接以增快速度，像下圖這個矩陣，就可以轉為下下圖。
      
      喔對，忘記說一件事情，為了達到快速的效率，我們使用的是十字Link List，所以需要四個東西R[][]，L[][]，U[][]，D[][]（上下左右），然後為了其中使用上的方便，我們會多增加一個S[]，代表每列有幾個點。再來就是，除了下圖這些點，還需要多m個點（矩陣為n*m），代表著整列，並要加上一個header，也就是一切的總指揮（類似），建完圖後大致就如下下圖所示。（這樣我就寫了30行，真是有點難建）

       再來要講的就是刪除列跟插入列了，除了原本的兩式可以把整列跳掉，還要順便把那列為1的row一同砍掉。而輸入就是刪除的反操作。最後就只剩下DFS內容了，內容很簡單，先找出有最少1的列（使分支度降低），將此列滿足（用for）將每種都跑過一遍，並將跟所選row有重疊的row一併刪除，如此遞迴下去，及得所求。

http://codepad.org/kqDiKX4V

許許多多的參考資料都可以在網路上取得～