程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int MAXN = 600;
const int MAXM = MAXN * MAXN * 2;
bool valid[2][MAXN][MAXN];

// A stat can represents a situation.
struct stat {
  // Number of businessman in the start bank.
  int bMan;
  // Number of servant in the start bank.
  int servant;
  // Whether current stat is in the start bank.
  bool start;
};

// A single step indicates how they moves.
struct step {
  int bMan;
  int servant;
};
stat stats[MAXM];
step steps[2][MAXN][MAXN];

// Whether a stats is valid.
bool isValid(const stat& s, int n) {
  int bMan = s.bMan, servant = s.servant;
  if(bMan < 0 || bMan > n || servant < 0 || servant > n) {
    return false;
  }
  if(bMan > 0 && servant > bMan) {
    return false;
  }
  if(bMan < n && n - servant > n - bMan) {
    return false;
  }
  return true;
}

// Tests for n businessmen and n servants whether there are ways to move safely.
bool test(int n) {
  int head = 0, tail = 0, i, j, bMan = n, servant = n, start = true;
  step currStep;
  stat tmp;
  // Initializes.
  memset(valid, 0, sizeof(valid));
  valid[start][bMan][servant] = true;
  stat curr;
  curr.bMan = bMan;
  curr.servant = servant;
  curr.start = start;
  stats[tail++] = curr;

  // BFS all possible status.
  while(head < tail) {
    curr = stats[head++];
    if(curr.bMan == 0 && curr.servant == 0 && !curr.start) {
      break;
    }
    for(i = 0; i <= 2; ++i) {
      for(j = i ? 0 : 1; i + j <= 2; ++j) {
        tmp = curr;
        tmp.start = !tmp.start;
        if(curr.start) {
          tmp.bMan -= i;
          tmp.servant -= j;
        } else {
          tmp.bMan += i;
          tmp.servant += j;
        }
        if(isValid(tmp, n)) {
          bMan = tmp.bMan;
          servant = tmp.servant;
          start = tmp.start;
          if(!valid[start][bMan][servant]) {
            currStep.bMan = i;
            currStep.servant = j;
            steps[start][bMan][servant] = currStep;
            stats[tail++] = tmp;
          }
          valid[start][bMan][servant] = true;
        }
      }
    }
  }
  return valid[0][0][0];
}

int main() {
  int n;
  int bMan = 0, servant = 0, start = false;
  step currStep;
  scanf("%d", &n);
  if(!test(n)) {
    printf("No\n");
    return 0;
  }
  printf("\tbMan\tservant\n");
  while(bMan != n || servant != n || !start) {
    currStep = steps[start][bMan][servant];
    printf("%s\t%d\t%d\n", start ? "Back" : "Go", currStep.bMan, currStep.servant);
    if(!start) {
      bMan += currStep.bMan;
      servant += currStep.servant;
    } else {
      bMan -= currStep.bMan;
      servant -= currStep.servant;
    }
    start = !start;
  }
  return 0;
}

程序代码：

#include <stdio.h>

void show(int s)
{
    printf("{m:%d, s:%d} %s {m:%d, s:%d}\n",
        (s>>4)&3, (s>>1)&3, (s&1?"~!":"!~"),(s>>10)&3, (s>>7)&3);
}

int search(int * ss, int es)
{
    const int m[] = {0x7E,0xFC,0x3F0,0x7E0,0x46E};
    static char f[0x40];
    int s, c, t, i;

    if(*ss == es) return 1;
    f[*ss & 0x3F] = 1;
    for(i = 0; i < sizeof(m) / sizeof(m[0]); i++)
    {
        t = s = *ss + (*ss & 1 ? -m[i] : m[i]) ^ 1;
        if((t & 0x1248) != 0x1248) continue;
        t |= ((s >> 4 & 3) ? 0 : 0x30) | ((s >> 10 & 3) ? 0 : 0xC00);
        if(((t - ((t & 0x186) << 3)) & 0x1248) != 0x1248) continue;
        if(f[s & 0x3F]) continue;
        ss[1] = s;
        c = search(ss + 1, es);
        if(c > 0){ f[*ss & 0x3F] = 0; return c + 1;}
    }
    f[*ss & 0x3F] = 0;
    return 0;
}

int main()
{
    int ss[16] = {0x127E}, es = 0x1FC9, c, i;

    c = search(ss, es);
    for(i = 0; i < c; show(ss[i++]));
    return 0;
}