#include <iostream.h>
#include <string>
#include <hash_set.h>
#define SZ 5

/* int grid[SZ*SZ] = {
  1,-1, 2,-1, 3,
 -1,-1,-1,-1,-1,
  4,-1,-1,-1,-1,
 -1,-1,-1,-1,-1,
  5,-1,-1,-1, 0}; */

hash_set<long> states;
string sofar;
int loc[6] = {24,0,2,4,10,20};
char dirs[4] = {'n','s','w','e'};
int dinc[4] = {-SZ,SZ,-1,1};
char shipname[6] = {'X','A','B','C','D','E'};

long getstate(void) {
  long ans=0;
  for (int lcv=0;lcv<6;lcv++) {
    ans *= SZ*SZ;
    ans += loc[lcv];
  }
  return(ans);
}

void print (void) {
  cout << "************";
  for (int lcv=0;lcv<SZ*SZ;lcv++) {
    bool found = false;
    if (lcv%5==0) cout << "*\n* ";
    for (int shp=0;shp<6;shp++) if (lcv == loc[shp]) {
      cout << shipname[shp] << " "; 
      found = true;
    }
    if (!found) cout << "- ";
  }
  cout << "*\n*************\n\n";
}

void printmove(int ship,int dir) {
  cout << shipname[ship] << dirs[dir];
}

bool iswall(int check,int dir) {
  switch (dir) {
    case 0: return(check<0); break;
    case 1: return(check>=SZ*SZ); break;
    case 2: return((check+1)%SZ==0); break;
    case 3: return(check%SZ==0); break;
  }
}
 
bool isship(int check) {
  for (int shp=0;shp<6;shp++) if (loc[shp]==check) return (true);
  return (false);
}

bool moveifable(int ship,int dir) {
  int dincrement = dinc[dir];
  int testloc = loc[ship]+dincrement;
  if (iswall(testloc,dir)) return (false);
  if (isship(testloc)) return (false);
  while (!iswall(testloc+dincrement,dir) && !isship(testloc+dincrement)) 
    testloc += dincrement;
  if (iswall(testloc+dincrement,dir)) return (false);
  else { // is ship
    loc[ship]=testloc;
    return (true);
  }
}

void recurse (int turn) {
  // cout << "push\n";
  if (turn<3)
  cout << sofar << "\n";
  // print();
  if (loc[0]==12) // solved
    cout << turn << "-moves: " << sofar << "\n";
  else for (int ship=0;ship<6;ship++) {
    int shiploc = loc[ship];
    for (int dir=0;dir<4;dir++) if (moveifable(ship,dir)) {
      sofar += shipname[ship];
      sofar += dirs[dir];
      if (states.find(getstate()) == states.end()) {
        states.insert(getstate());
        recurse(turn+1);
      } else {
        // cout << "Repeat: " << sofar << "\n";
      }
      sofar.resize(turn*2);
      loc[ship]=shiploc;
    }
  }
  // cout << "pop\n";
}

void main (void) {
  recurse(0);
}