151121

C


Self-avoiding walk(5)

m x n を調べた。
（実行時間は1時間半ほどかかる。）
なお、3 ≦ m ≦ 6 のときについて、
オンライン整数列大辞典の
A006192（http://oeis.org/A006192/list）、
A007786（http://oeis.org/A007786/list）、
A007787（http://oeis.org/A007787/list）、
A145403（http://oeis.org/A145403/list）
に詳しく載っている。
また、次のページも詳しい。
http://www.iwriteiam.nl/Crook_path.html

#include <stdio.h>

// startがx, y、goalがw - 1, h - 1
long long search(int x, int y, int w, int h, long long used, int depth){
 long long cnt = 0LL;
 if (x < 0 || w <= x || y < 0 || h <= y || (used & (1LL << (x + y * w))) > 0) return 0;
 if (x == w - 1 && y == h - 1) 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 main(void){
 int i;
 int j;
 long long used;
 for (i = 2; i < 10; i++){
  for (j = 1; j < 7; j++){
   used = 0LL;
   printf("%lld\n", search(0, 0, i, j, used, 1));
  }
 }
 return 0;
}

出力結果
1
2
4
8
16
32
1
4
12
38
125
414
1
8
38
184
976
5382
1
16
125
976
8512
79384
1
32
414
5382
79384
1262816
1
64
1369
29739
752061
20562673
1
128
4522
163496
7110272
336067810
1
256
14934
896476
67005561
5493330332