最省納智捷1年新車83萬起工程師靠存股年領百萬股息輕忽小中風,當心變殘障破戒!比丘吃葷 連3次...
2012-04-27 21:04:35 人氣(340) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][EulerianGraph] 291 - The House Of Santa Claus

0
收藏
0
推薦


 The House Of Santa Claus 

In your childhood you most likely had to solve the riddle of the house of Santa Claus. Do you remember that the importance was on drawing the house in a stretch without lifting the pencil and not drawing a line twice? As a reminder it has to look like shown in Figure 1.

  figure20
Figure: The House of Santa Claus

Well, a couple of years later, like now, you have to ``draw'' the house again but on the computer. As one possibility is not enough, we require all the possibilities when starting in the lower left corner. Follow the example in Figure 2 while defining your stretch.

  figure33
Figure: This Sequence would give the Outputline 153125432

All the possibilities have to be listed in the outputfile by increasing order, meaning that 1234... is listed before 1235... .

Output

So, an outputfile could look like this:

12435123
13245123
...
15123421



#include <stdio.h>
int map[5][5] = {
    {0,1,1,0,1},
    {1,0,1,0,1},
    {1,1,0,1,1},
    {0,0,1,0,1},
    {1,1,1,1,0}
    };
int ans[8] = {0};
void DFS(int idx, int now) {
    ans[idx] = now;
    if(idx == 8) {
        for(int i = 0; i < 9; i++)
            printf("%d", ans[i]+1);
        puts("");
        return ;
    }
    int i;
    for(i = 0; i < 5; i++) {
        if(map[now][i] == 1) {
            map[now][i] = map[i][now] = 0;
            DFS(idx+1, i);
            map[now][i] = map[i][now] = 1;
        }
    }
}
int main() {
    DFS(0, 0);
    return 0;

}

291The House Of Santa ClausEulerianGraph
台長:Morris
人氣(340) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][DP最大值最小化] 714 - Copying Books
此分類上一篇:[UVA][MaxFlow/MinCut] 10480 - Sabotage

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文