12a.c

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