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)
  55 {
  56         if (strcmp(node->key, "end") == 0)
  57                 return 1;
  58         if (islower(node->key[0])) {
  59                 for (int i = 0; i<nvisited; i++)
  60                         if (strcmp(node->key, visited[i]) == 0)
  61                                 return 0;
  62                 visited = realloc(visited, sizeof(char *)*(nvisited+1));
  63                 visited[nvisited++] = node->key;
  64         }
  65         int r = 0;
  66         for (struct conn *c = node->connections; c != NULL; c = c->hh.next) {
  67                 if (twice && strcmp(node->key, "start") != 0 && islower(node->key[0]))
  68                         r += find_end(c->node, copy_visited(visited, nvisited-1), nvisited-1, false);
  69                 r += find_end(c->node, copy_visited(visited, nvisited), nvisited, twice);
  70         }
  71         free(visited);
  72         return r;
  73 }
  74
  75 int main()
  76 {
  77         struct node *graph = NULL;
  78         char *buf = NULL;
  79         size_t len = 0;
  80         while (getline(&buf, &len, stdin) != -1) {
  81                 char *toname = strchr(buf, '-');
  82                 *(toname++)= '\0';
  83                 if (toname[strlen(toname)-1] == '\n')
  84                         toname[strlen(toname)-1] = '\0';
  85                 add_connection(get_or_create(&graph, buf),
  86                                get_or_create(&graph, toname));
  87         }
  88
  89         printf("%d\n", find_end(get_or_create(&graph, "start"), NULL, 0, true));
  90 }