12b.c

   1 #include <stdio.h>
   2 #include <ctype.h>
   3 #include <stdbool.h>
   4
   5 #include <uthash.h>
   6
   7 struct conn {
   8         char key[10];
   9         struct node *node;
  10         UT_hash_handle hh;
  11 };
  12 struct node {
  13         char key[10];
  14         struct conn *connections;
  15         UT_hash_handle hh;
  16 };
  17
  18 struct node *get_or_create(struct node **graph, char name[])
  19 {
  20         struct node *n;
  21         HASH_FIND_STR(*graph, name, n);
  22         if (n) {
  23                 return n;
  24         } else {
  25                 n = malloc(sizeof(struct node));
  26                 strcpy(n->key, name);
  27                 n->connections = NULL;
  28                 HASH_ADD_STR(*graph, key, n);
  29         }
  30         return n;
  31 }
  32
  33 void add_connection(struct node *from, struct node *to)
  34 {
  35         //to
  36         struct conn *c = malloc(sizeof(struct conn));
  37         strcpy(c->key, to->key);
  38         c->node = to;
  39         HASH_ADD_STR(from->connections, key, c);
  40         //fro
  41         c = malloc(sizeof(struct conn));
  42         strcpy(c->key, from->key);
  43         c->node = from;
  44         HASH_ADD_STR(to->connections, key, c);
  45 }
  46
  47 char **copy_visited(char **visited, int nvisited)
  48 {
  49         char **r = malloc(sizeof(char *)*nvisited);
  50         memcpy(r, visited, sizeof(char *)*nvisited);
  51         return r;
  52 }
  53
  54 int find_end(struct node *node, char **visited, int nvisited, bool twice, char **path, int npath)
  55 {
  56         if (strcmp(node->key, "end") == 0) {
  57                 printf("path: ");
  58                 for (int i = 0; i<npath; i++)
  59                         printf("%s,", path[i]);
  60                 printf("\n");
  61                 return 1;
  62         }
  63         if (islower(node->key[0])) {
  64                 for (int i = 0; i<nvisited; i++)
  65                         if (strcmp(node->key, visited[i]) == 0)
  66                                 return 0;
  67                 visited = realloc(visited, sizeof(char *)*(nvisited+1));
  68                 visited[nvisited++] = node->key;
  69         }
  70         path = realloc(path, sizeof(char *)*(npath+1));
  71         path[npath++] = node->key;
  72         int r = 0;
  73         for (struct conn *c = node->connections; c != NULL; c = c->hh.next) {
  74                 if (twice && strcmp(node->key, "start") != 0 && islower(node->key[0]))
  75                         r += find_end(c->node, copy_visited(visited, nvisited-1), nvisited-1, false, copy_visited(path, npath), npath);
  76                 r += find_end(c->node, copy_visited(visited, nvisited), nvisited, twice, copy_visited(path, npath), npath);
  77         }
  78         free(visited);
  79         return r;
  80 }
  81
  82 int main()
  83 {
  84         struct node *graph = NULL;
  85         char *buf = NULL;
  86         size_t len = 0;
  87         while (getline(&buf, &len, stdin) != -1) {
  88                 char *toname = strchr(buf, '-');
  89                 *(toname++)= '\0';
  90                 if (toname[strlen(toname)-1] == '\n')
  91                         toname[strlen(toname)-1] = '\0';
  92                 add_connection(get_or_create(&graph, buf),
  93                                get_or_create(&graph, toname));
  94         }
  95
  96         find_end(get_or_create(&graph, "start"), NULL, 0, true, NULL, 0);
  97 //      printf("%d\n", find_end(get_or_create(&graph, "start"), NULL, 0, true, NULL, 0));
  98 }