Problem Solving►UVa

UVa 291 - The House Of Santa Claus

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

直接對每個點做 DFS ，用 used[][] 記錄每條邊的使用狀況和順序，最後印出來即可。

Code

UVa 291
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>

const int adjList[6][5] = { {},{ 2, 3, 5 }, { 1, 3, 5 }, { 1, 2, 4, 5 }, { 3, 5 }, { 1, 2, 3, 4 } };
int order[9];
bool used[6][6];
void solve(int pre, int n)
{
    if (n == 9)
    {
        for (int i = 0; i < 9; i++)
            printf("%d", order[i]);
        putchar('\n');
    }
    else
    {
        for (int j = 0; adjList[pre][j]; j++)
        {
            if (!used[pre][adjList[pre][j]])
            {
                used[adjList[pre][j]][pre] = used[pre][adjList[pre][j]] = true;
                order[n] = adjList[pre][j];

                solve(adjList[pre][j], n + 1);

                used[adjList[pre][j]][pre] = used[pre][adjList[pre][j]] = false;
            }
        }

    }
}
int main()
{
    order[0] = 1;
    solve(1, 1);
    return 0;
}