ACM 291 The House Of Santa Claus

一筆劃問題。
相對於以點(vertex)為準的dfs，做以線(edge)為準的dfs即可。

不過問題就來了，如何表示edge是否走訪呢？
我的作法是做一個visited[MAXEDGE]，
接著在graph的struct中增加一筆pos資料，
表示edge所在visited的位置。
從vertex 1開始走訪，
每次都判斷是否還有edge可以走訪，
若有就繼續走，走到edge == 9即可。
（共8個點，所以走到第九次就要output）

話說關於graph的問題我都用adjancency list去做，
從來沒用過adjancency martix，在這裡，
看到人家用adjancency martix的解法……真是為之驚嘆！
看來我殺雞用牛刀，開太空梭買菜了 -_-。

所以其實也可以做以點為準的dfs，
但是要紀錄的是edge，走訪到第九層就做output + return即可。
用一個二維陣列做graph，另一個二維陣列做edge紀錄！
偉哉adjancency martix！

所以重點其實是紀錄點或是紀錄線嘛……

/* ACM 291 The House Of Santa Claus
 * mythnc
 * 2012/01/13 18:53:08   
 * run time: 0.004
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXEDGE 8
#define MAXNODE 6 /* Node 0~5 */

typedef struct node {
    /* pos: edge position */
    int pos, node;
    struct node *next;
} Node;

typedef enum {FALSE = 0, TRUE} bool;

void init(int, int, int);
void backtrack(int, int);
void freeg(void);

Node *g[MAXNODE] = {NULL};
/* record edge is visited or not */
bool visited[MAXEDGE];
char output[MAXEDGE + 1];

int main(void)
{
    int i;

    init(1, 2, 0);
    init(2, 1, 0);
    init(1, 3, 1);
    init(3, 1, 1);
    init(1, 5, 2);
    init(5, 1, 2);
    init(2, 3, 3);
    init(3, 2, 3);
    init(2, 5, 4);
    init(5, 2, 4);
    init(3, 4, 5);
    init(4, 3, 5);
    init(3, 5, 6);
    init(5, 3, 6);
    init(4, 5, 7);
    init(5, 4, 7);

    output[0] = 1 + '0';
    backtrack(1, 1);
    freeg();

    return 0;
}

/* init: initialize graph */
void init(int v1, int v2, int pos)
{
    Node *pt, *tmp;

    tmp = (Node *)malloc(sizeof(Node));
    tmp->next = NULL;
    tmp->node = v2;
    tmp->pos = pos;

    if (g[v1] == NULL) {
        g[v1] = tmp;
        return;
    }
    pt = g[v1];
    while (pt->next != NULL)
        pt = pt->next;
    pt->next = tmp;
}

/* backtrack: use backtracking method to output answer */
void backtrack(int index, int node)
{
    Node *pt;
    int pos;

    if (index == MAXEDGE + 1) {
        output[index] = '\0';
        printf("%s\n", output);
        return;
    }

    for (pt = g[node]; pt; pt = pt->next) {
        pos = pt->pos;
        node = pt->node;
        if (!visited[pos]) {
            visited[pos] = TRUE;
            output[index] = node + '0';
            backtrack(index + 1, node);
            visited[pos] = FALSE;
        }
    }
}

/* freeg: free all graph node */
void freeg(void)
{
    Node *pt, *tmp;
    int i;

    for (i = 0; i < MAXNODE; i++) {
        pt = g[i];
        while (pt != NULL) {
            tmp = pt;
            pt = pt->next;
            free(tmp);
        }
    }
}