464B - Restore Cube

jd3 · 發表於 2014-9-23 23:14:53

題意：有正立方體頂點座標(8個) ，但是座標點的x,y,z可能是對調的(不同點之間不對調)，求原本的正立方體頂點座標(任一解或無解)

方法：暴力
基本上就是dfs下去
要枚舉所有點的排列情況
這DFS怎麼樣比較好寫呢?
這裡有一個交換方法枚舉一個點的所有排列(6種)

交換次序如下

原本 -> 123
213
312
132
231
321
回到 -> 123

其實其中的數學原理我並不懂(待高手補充)
總之交換順序就是第1,2交換;第1,3交換;第1,2交換;第1,3交換......
因為會回到原點，所以沒什麼後遺症，只要每一層遞迴for寫下去就對了
像這樣，找到答案就 return 了不要真的枚舉完

[C++] 純文本查看 復制代碼

for(int i = 1 ; i <= 6 ; i++)

        {

                swap(point[p][0], point[p][2-(i&1)]);

                if(p==7)

                {

                        if(check_cube())

                                return true;

                }

                else if(dfs(p+1))

                        return true;

        }

        return false;

最後要檢查是否是正立方體
方法是利用邊長
所有點對之間的邊長長度只有3種，數量也是固定的
暴力的下去判斷他(但也別把常數搞得太大)
還有邊長可以存平方避免sqrt下去會有浮點誤差問題

記得開long long

AC CODE:

購買主題本主題需向作者支付 1 枚金幣 才能瀏覽

[CF] 464B - Restore Cube

台南一中資訊社

程式設計達人 - 2014