151114

C


Number of directed Hamiltonian paths in mxn grid graph(1)

m = 2 のときを調べる。
なお、オンライン整数列大辞典の
A137882 のCOMMENTSには
n > 1 のとき、2 * (n^2 - n + 2)
となることが載っている。

#include <stdio.h>

int search(int x, int y, int w, int h, long long used, int depth){
 int cnt = 0;
 if (x < 0 || w <= x || y < 0 || h <= y || (used & (1LL << (x + y * w))) > 0) return 0;
 if (depth == w * h) return 1;
 used += 1LL << (x + y * w);
 cnt += search(x + 1, y, w, h, used, depth + 1);
 cnt += search(x - 1, y, w, h, used, depth + 1);
 cnt += search(x, y + 1, w, h, used, depth + 1);
 cnt += search(x, y - 1, w, h, used, depth + 1);
 used -= 1LL << (x + y * w);
 return cnt;
}

int directed_Hamiltonian_paths(int w, int h){
 int x;
 int y;
 long long used;
 int total = 0;
 for (y = 0; y < h / 2; y++){
  for (x = 0; x < w / 2; x++){
   used = 0LL;
   total += search(x, y, w, h, used, 1) * 4;
  }
  if (w % 2 == 1){
   x = w / 2;
   used = 0LL;
   total += search(x, y, w, h, used, 1) * 2;
  }
 }
 if (h % 2 == 1){
  y = h / 2;
  for (x = 0; x < w / 2; x++){
   used = 0LL;
   total += search(x, y, w, h, used, 1) * 2;
  }
  if (w % 2 == 1){
   x = w / 2;
   used = 0LL;
   total += search(x, y, w, h, used, 1) * 1;
  }
 }
 return total;
}

int main(void){
 int h;
 for (h = 1; h < 31; h++){
  printf("%d\n", directed_Hamiltonian_paths(2, h));
 }
 return 0;
}

出力結果
2
8
16
28
44
64
88
116
148
184
224
268
316
368
424
484
548
616
688
764
844
928
1016
1108
1204
1304
1408
1516
1628
1744