当前正在枚举的path的最大长度是N，所以visited数组只需要尺寸是[N]就行，搞成二维的[N][N]也行。

每个点的下一个邻接点最多只有3个，因为不能回到来时的路。

N = 1, path count: 1 (1.00), time: 0.000 seconds
N = 2, path count: 2 (2.00), time: 0.000 seconds
N = 3, path count: 5 (2.50), time: 0.000 seconds
N = 4, path count: 12 (2.40), time: 0.000 seconds
N = 5, path count: 30 (2.50), time: 0.000 seconds
N = 6, path count: 73 (2.43), time: 0.000 seconds
N = 7, path count: 183 (2.51), time: 0.000 seconds
N = 8, path count: 456 (2.49), time: 0.000 seconds
N = 9, path count: 1151 (2.52), time: 0.000 seconds
N = 10, path count: 2900 (2.52), time: 0.000 seconds
N = 11, path count: 7361 (2.54), time: 0.000 seconds
N = 12, path count: 18684 (2.54), time: 0.000 seconds
N = 13, path count: 47652 (2.55), time: 0.000 seconds
N = 14, path count: 121584 (2.55), time: 0.001 seconds
N = 15, path count: 311259 (2.56), time: 0.002 seconds
N = 16, path count: 797311 (2.56), time: 0.006 seconds
N = 17, path count: 2047384 (2.57), time: 0.014 seconds
N = 18, path count: 5260692 (2.57), time: 0.037 seconds
N = 19, path count: 13542718 (2.57), time: 0.094 seconds
N = 20, path count: 34884239 (2.58), time: 0.244 seconds
N = 21, path count: 89991344 (2.58), time: 0.624 seconds
N = 22, path count: 232282110 (2.58), time: 1.610 seconds
N = 23, path count: 600281932 (2.58), time: 4.166 seconds
N = 24, path count: 1552096361 (2.59), time: 10.763 seconds
N = 25, path count: 4017128206 (2.59), time: 27.799 seconds

CPU是3700X

#include <stdint.h>
#include <stdio.h>
#include <windows.h>

#pragma pack(push, 1)
struct Point {
  uint8_t x;
  uint8_t y;
};
#pragma pack(pop)

static constexpr uint8_t MAX_LATTICE_LEN = 25;

static uint8_t N = 1;
static uint32_t pathCount = 0;
static bool visited[MAX_LATTICE_LEN * MAX_LATTICE_LEN];
static uint8_t visitedLen = 0;

__forceinline uint16_t GetIndex(uint8_t x, uint8_t y) {
  return (uint16_t)x + (uint16_t)y * (uint16_t)N;
}

__forceinline void SetVisited(uint8_t x, uint8_t y) {
  visited[GetIndex(x, y)] = true;
  visitedLen++;
}

__forceinline void SetNotVisited(uint8_t x, uint8_t y) {
  visited[GetIndex(x, y)] = false;
  visitedLen--;
}

__forceinline bool IsVisited(uint8_t x, uint8_t y) {
  return visited[GetIndex(x, y)];
}

__forceinline bool GetLeftMove(const Point &point, Point &child) {
  uint8_t x = point.x;
  uint8_t y = point.y;

  if (x > 0 && !IsVisited(--x, y)) {
    child.x = x;
    child.y = y;
    return true;
  }

  return false;
}

__forceinline bool GetRightMove(const Point &point, Point &child) {
  uint8_t x = point.x;
  uint8_t y = point.y;

  if (x < N && !IsVisited(++x, y)) {
    child.x = x;
    child.y = y;
    return true;
  }

  return false;
}

__forceinline bool GetUpMove(const Point &point, Point &child) {
  uint8_t x = point.x;
  uint8_t y = point.y;

  if (y < N && !IsVisited(x, ++y)) {
    child.x = x;
    child.y = y;
    return true;
  }

  return false;
}

__forceinline bool GetDownMove(const Point &point, Point &child) {
  uint8_t x = point.x;
  uint8_t y = point.y;

  if (y > 0 && !IsVisited(x, --y)) {
    child.x = x;
    child.y = y;
    return true;
  }

  return false;
}

__forceinline void CountPath(const Point &point);

__forceinline void VisitChild(const Point &child) {
  SetVisited(child.x, child.y);
  CountPath(child);
  SetNotVisited(child.x, child.y);
}

__forceinline void CountPath(const Point &point) {
  uint8_t len = visitedLen;
  if (len == N) {
    ++pathCount;
    return;
  }

  Point child;

  if (GetRightMove(point, child)) {
    if (len == (N - 1)) {
      ++pathCount;
    } else {
      VisitChild(child);
    }
  }

  if (GetUpMove(point, child)) {
    if (len == (N - 1)) {
      ++pathCount;
    } else {
      VisitChild(child);
    }
  }

  if (GetLeftMove(point, child)) {
    if (len == (N - 1)) {
      ++pathCount;
    } else {
      VisitChild(child);
    }
  }

  if (GetDownMove(point, child)) {
    if (len == (N - 1)) {
      ++pathCount;
    } else {
      VisitChild(child);
    }
  }
}

int main(int argc, char **argv) {
  LARGE_INTEGER frequency;
  QueryPerformanceFrequency(&frequency);

  Point root{0, 0};
  Point child{1, 0};

  uint32_t prevCount = 1;

  for (N = 1; N <= MAX_LATTICE_LEN; ++N) {
    pathCount = 0;

    memset(visited, 0, (uint16_t)N * (uint16_t)N);
    SetVisited(0, 0);
    SetVisited(1, 0);

    visitedLen = 1;

    LARGE_INTEGER start;
    QueryPerformanceCounter(&start);

    CountPath(child);

    LARGE_INTEGER end;
    QueryPerformanceCounter(&end);

    double time = ((double)end.QuadPart - (double)start.QuadPart) /
                  (double)frequency.QuadPart;
    printf("N = %u, path count: %u (%.2f), time: %.3f seconds\n", (uint32_t)N,
           pathCount, (double)pathCount / (double)prevCount, time);

    prevCount = pathCount;
  }

  return 0;
}

【 在 stub 的大作中提到: 】
: visited的key是什么呢，点不能复用。你在该点之前记录的数据，由于这一次跟上一次路过的痕迹已经不同。所以记录的是否有用么
--
FROM 221.222.172.*