题解

dfs(x,y)：当前已经站在 (x,y)，继续搜索所有到终点的合法方案。

本题的 vis 表示“格子是否在当前路径中”。同一个格子可以出现在不同方案里，因此递归返回后必须撤销标记：

vis[nx][ny] = true;
dfs(nx, ny);
vis[nx][ny] = false;

到达终点时找到一条完整方案，ans++ 后立即 return。

最坏复杂度为指数级，但网格最多 5×5。