#include <stdlib.h> 

struct csucs {
  struct csucs *siblings[4];
  int state; // 0 - unknown, 1 - known
  int festett;
  int elfestes[4];
};

struct pont {
  int x;
  int y;
};

struct csucslista {
  struct pont cim;
  struct csucs* cs;
  struct csucslista* next;
};


struct csucs *new_csucs() {
  struct csucs * cs = malloc(sizeof(struct csucs));
  cs->state=0;
  cs->festett=0;
  cs->siblings[0]=NULL;
  cs->siblings[1]=NULL;
  cs->siblings[2]=NULL;
  cs->siblings[3]=NULL;
  cs->elfestes[0]=0;
  cs->elfestes[1]=0;
  cs->elfestes[2]=0;
  cs->elfestes[3]=0;
  return cs;
}

void elfest(struct csucs *cs, int dir) {
  cs->elfestes[dir]++;
  cs->siblings[dir]->elfestes[(dir+4-2)%4]++;
}

struct pont pont_move(struct pont from, int dir) {
  switch (dir) {
  case 0: from.y++; break;
  case 1: from.x--; break;
  case 2: from.y--; break;
  case 3: from.x++; break;
  }
  return from;
}

struct csucs* csucs_move(struct csucs* from, int dir) {
  return from->siblings[dir];
}

struct csucslista* cslist_add(struct csucslista* csfej, struct pont poz, struct csucs *cs) {
  struct csucslista *ncs=malloc(sizeof(struct csucslista));

  ncs->next=csfej;
  ncs->cim=poz;
  ncs->cs=cs;
  return ncs;
}

struct csucs* cslist_search(struct csucslista *csfej, struct pont p) {
  struct csucslista *prev;
  for (prev=csfej;csfej!=NULL;prev=csfej, csfej=csfej->next) {
    if (p.x==csfej->cim.x && csfej->cim.y==p.y) {
      return csfej->cs;
    }
  }
  prev->next=cslist_add(NULL, p, new_csucs());
  return prev->next->cs;
}

void known_csucs(struct csucs *cs, char* fromwhat, int dir, struct pont poz, struct csucslista* csfej, int quick) {
  if (cs->state==0) {
    cs->state=1;
    if (fromwhat[1]=='1') {
      if (!cs->siblings[dir]) {
	cs->siblings[dir]=cslist_search(csfej, pont_move(poz, dir));
	cs->siblings[dir]->siblings[(dir+2)%4]=cs;
      }
      if (quick && cs->siblings[dir]->state==1) {
	elfest(cs, dir);
	elfest(cs, dir);
      }
    }
    if (fromwhat[0]=='1') {
      if (!cs->siblings[(dir-1+4)%4]) {
	cs->siblings[(dir-1+4)%4]=cslist_search(csfej, pont_move(poz, (dir-1+4)%4));
	cs->siblings[(dir-1+4)%4]->siblings[((dir-1+4)%4+2)%4]=cs;
      }
      if (quick && cs->siblings[(dir-1+4)%4]->state==1) {
	elfest(cs, (dir-1+4)%4);
	elfest(cs, (dir-1+4)%4);
      }
    }
    if (fromwhat[2]=='1') {
      if (!cs->siblings[(dir+1)%4]) {
	cs->siblings[(dir+1)%4]=cslist_search(csfej, pont_move(poz, (dir+1)%4));
	cs->siblings[(dir+1)%4]->siblings[((dir+1)%4+2)%4]=cs;
      }
      if (quick && cs->siblings[(dir+1)%4]->state==1) {
	elfest(cs, (dir+1)%4);
	elfest(cs, (dir+1)%4);
      }
    }
  }
}

/*
void cslist_dump(struct csucslista *csfej) {
  printf("** CSLIST_PRINT BEGIN\n");
  for (;csfej!=NULL;csfej=csfej->next) {
    printf("csucs: (%d, %d)\n", csfej->cim.x, csfej->cim.y);
  }
  printf("** CSLIST_PRINT END\n");
}
*/

int csucs_dump(struct csucs* start, char *res, int offset, int festes) {
  if (start==NULL) {
    res[offset]='0';
    return 1;
  }
  if (start->festett==festes) {
    res[offset]='x';
    return 1;
  }
  start->festett=festes;
  if (start->state==0) {
    res[offset]='u';
    return 1;
  } else {
    int o=offset;
    res[o++]='{';
    res[o++]=97+start->elfestes[0];
    o+=csucs_dump(start->siblings[0], res, o, festes);
    res[o++]=97+start->elfestes[1];
    o+=csucs_dump(start->siblings[1], res, o, festes);
    res[o++]=97+start->elfestes[2];
    o+=csucs_dump(start->siblings[2], res, o, festes);
    res[o++]=97+start->elfestes[3];
    o+=csucs_dump(start->siblings[3], res, o, festes);
    res[o++]='}';
    return o-offset;
  }
}