151122

C


直角二等辺三角形の形をした領域内のSelf-avoiding walk(2)

以下の方法は速いが、nが11までしか求まらない。

#include <stdio.h>

int triangular_number(int x, int y, int n){
 int i;
 i = x + (2 * n - y + 1) * y / 2;
 return i;
}

// startがx, y、goalの座標の和がn - 1
long long search(int x, int y, int n, long long used){
 long long cnt = 0LL;
 int z;
 z = triangular_number(x, y, n);
 if (x < 0 || n <= x || y < 0 || n <= y || (used & (1LL << z)) > 0) return 0;
 if (x + y == n - 1) return 1;
 used += 1LL << z;
 cnt += search(x + 1, y, n, used);
 cnt += search(x - 1, y, n, used);
 cnt += search(x, y + 1, n, used);
 cnt += search(x, y - 1, n, used);
 used -= 1LL << z;
 return cnt;
}

int main(void){
 int n;
 long long used;
 for (n = 1; n < 12; n++){
  used = 0LL;
  printf("%lld\n", search(0, 0, n, used));
 }
 return 0;
}

出力結果
1
2
4
12
48
288
2768
45408
1289000
63234984
5356226560