2012年4月21日 星期六

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
許許多多的參考資料都可以在網路上取得~

1 則留言: