第27回オフラインリアルタイムどう書く「分岐と行き止まり」の C言語による実装

// clang -std=c99 -Wall solve.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

struct ans{  char m[ 3*9 ]; };

bool can_go( char from, char to, char const * src )
{
  if ( strchr( src, from ) ){
    return false;
  }
  if ( from==to ){
    return true;
  }
  char * ways[] = {
    "1ag", "ab", "bc5", "c46",
    "2dh", "dec", "e5",
    "3bf", "fg", "gceh", "h4i", "i6", 0
  };
  for( int i=0 ; ways[i] ; ++i ){
    char const * way = ways[i];
    if ( from==way[0] ){
      for( int j=1 ; way[j] ; ++j ){
        if ( can_go( way[j], to, src )){
          return true;
        }
      }
    }
  }
  return false;
}

struct ans solve( char const * src )
{
  struct ans ans={{0}};
  for( char from='1' ; from<='3' ; ++from ){
    for( char to='4' ; to<='6' ; ++to ){
      if ( can_go( from, to, src ) ){
        if ( ans.m[0]!=0 ){
          strcat( ans.m, "," );
        }
        char path[3]={ from, to };
        strcat( ans.m, path );
      }
    }
  }
  if ( ans.m[0]==0 ){
    ans.m[0]='-';
  }
  return ans;
}

void test( char const * src, char const * expected )
{
  struct ans ans = solve( src );
  bool ok = strcmp( ans.m, expected )==0;
  printf( "%s : %s->%s ( %s )\n", 
    ( ok ? "ok" : "***NG***"),
    src, ans.m, expected );
}

int main()
{
/*0*/ test( "befi", "14,16,24,26" );
/* 中略 */
/*44*/ test( "bdefgi", "24" );
}