#include <stdio.h> #include <stdbool.h> #define N 17 // N >= 3 bool Node[2 * N + 1][N + 1]; unsigned long long Polygons; void step(unsigned n, int h, int v, int h_right, int h_left, int v_up) { if (Node[h][v]) return; if (n == 4 * N) { // one vertical step away from start a(-1, 2) or b( 1, 2) Polygons++; return; } Node[h][v] = true; if (n % 2) { // n odd: horizontal step if (h_right) step(n + 1, h + 1, v, h_right - 1, h_left, v_up); if (h_left) if (v > 1) step(n + 1, h - 1, v, h_right, h_left - 1, v_up); } else { // n even: vertical step if (v_up) step(n + 1, h, v + 1, h_right, h_left, v_up - 1); if (v) if (v > 1 || h > N) step(n + 1, h, v - 1, h_right, h_left, v_up); } Node[h][v] = false; } int main() // first two steps are fixed (N >= 3) { Node[N - 1][2] = true; // step 1a: (-1, 2) -> ( 0, 2) h right Node[N + 1][2] = true; // step 1b: ( 1, 2) -> ( 0, 2) h left Node[N + 0][2] = true; // step 2: ( 0, 2) -> ( 0, 1) v down step(3, N + 0, 1, N, N, N); // step 3 starts at ( 0, 1) printf("n=%d: %llu polygons.\n", N, Polygons); }