n匹とm匹がk匹乗りボートで川渡りする問題

#include <stdio.h> 
#include <stdlib.h> 

#define N 4 /* ネコの数 */ 
#define M 4 /* ネズミの数 */ 
#define K 3 /* ボートの定員 */ 

int np, solution; 
unsigned char nk[(K+1)*(K+2)/2], mk[(K+1)*(K+2)/2], 
   nh[2*(N+1)*(M+1)], mh[2*(N+1)*(M+1)], flag[N+1][M+1]; 

void found(int n) 
{ 
   int i; 
   static char cat[] = "CCCCCCCCCC", rat[] = "RRRRRRRRRR"; 

   printf("解 %d\n", ++solution); 
   for (i = 0; i <= n; i++) { 
      printf("%4d %-*.*s %-*.*s / %-*.*s %-*.*s\n", 
      i, N, nh[i], cat, M, mh[i], rat 
      N, N - nh[i], cat, M - mh[i], rat 
   } 
} 

void recursive(void) 
{ 
   static int i = 0; 
   int j, n, m; 

   i++; 
   for (j = 1; j < np; j++) { 
      if (i & 1) { 
         n = nh[i - 1] - nk[j]; 
         m = mh[i - 1] - mk[j]; 
      } else { 
         n = nh[i - 1] + nk[j]; 
         m = mh[i - 1] + mk[j]; 
      } 
      if (n < 0 || m < 0 || n > N || m > M || 
         (flag[n][m] & (1 << (i & 1)))) continue; 
         nh[i] = n; 
         mh[i] = m; 
         if (n == 0 && m == 0) found(i); 
      else { 
         flag[n][m] |= 1 << (i & 1); 
         recursive(); 
         flag[n][m] ^= 1 << (i & 1); 
      } 
   } 
   i--; 
} 

int main() 
{ 
   int n, m; 
   np = 0; 
   for (n = 0; n <= K; n++) for (m = 0; m <= K - n; m++) 
      if (n == 0 || n >= m) { 
         nk[np] = n; 
         mk[np] = m; 
         np++; 
      } 
      for (n = 0; n <= N; n++) for (m = 0; m <= M; m++) 
         if ((n > 0 && n < m) || (n < N && N - n < M - m)) 
            flag[n][m] |= 1 | 2; 
      nh[0] = N; mh[0] = M; 
      flag[N][M] |= 1; 
      solution = 0; 
      recursive(); 
   if (solution == 0) printf("解なし\n"); 
   return EXIT_SUCCESS; 
}