返回题解分享
讨论 / 题解分享/ 帖子详情

路径计数(结果填空) - 题解

#include <cstdio>
#include <vector>
#include <functional>

// #include <bits/stdc++.h>

using namespace std;

const int fx[4][2] = {
	{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};

int main() {
	const int n = 6;
	vector<vector<char>> vis(n, vector<char>(n, 0));
	int res = 0;
	function<void(int, int, int)> dfs = [&](int i, int j, int d) {
		if (i == 0 && j == 0 && d > 2 && d <= 12 && vis[i][j]) { // 小心 (0, 0) -> (0, 1) -> (0, 0) 这类路线(所以 d > 2) 
			++res;
			return;
		}
		
		if (i < 0 || j < 0 || i >= n || j >= n || vis[i][j] || d > 12)
			return;
		
		vis[i][j] = 1;
		
		for (const auto& it : fx) {
			dfs(i + it[0], j + it[1], d + 1);
		}
		
		vis[i][j] = 0;
	};
	
	dfs(0, 0, 0);
	
	printf("%d\n", res);
	
	return 0;
}
3 回复 0 转发 0 喜欢 6 阅读
回复 (3)
默认 最新
露米 2026/2/5
看到你的召唤啦,很高兴能继续陪你探讨这个问题 🙂

在尝试了对称性优化后,如果你还想让程序跑得更快一点,其实还有一个很直观的思路,叫做“曼哈顿距离剪枝”。

简单来说,因为我们最终要回到 (0,0),且总步数不能超过 12,那么在搜索的每一步,我们可以算一下:“当前已走步数” + “回到起点的最少步数(即横纵坐标绝对值之和)”。如果这个值已经超过了 12,说明这条路径无论如何都无法在规定步数内回到起点,这时就可以提前结束这一层的搜索了。

这种“预判”的小技巧在处理搜索类题目时非常有用,能帮程序省掉很多不必要的重复劳动。

你可以慢慢消化一下这个想法,不急着立刻实现。算法的学习就像走迷宫,每发现一个小技巧都是一种惊喜。如果在尝试的过程中有了新的感悟,或者代码运行效率有了明显的提升,随时记得跟我分享呀 🙂
我会一直在这里,为你每一次的小进步加油。祝你今天也过得愉快,在代码的世界里找到更多乐趣~
0
露米 2026/2/5
看到你的艾特啦,很高兴能继续和你交流 🙂

关于之前提到的对称性,其实在这个 6x6 的棋盘中,从 (0,0) 出发的第一步无论是向右走还是向下走,后续能形成的路径在结构上是完全对称的。

你可以尝试在代码里固定第一步的方向(比如强制第一步只往右走),算出结果后再乘以 2,这样搜索的工作量就能直接减少一半。在处理更大规模的搜索问题时,这种利用对称性来“剪枝”的小技巧往往能显著提升效率。

当然,目前的逻辑已经非常清晰严谨了,这对于结果填空题来说是最重要的。如果之后在尝试优化时有了新的想法,或者遇到了其他有趣的题目,随时欢迎再找我聊聊呀。

慢慢来,我会一直在这里陪伴你的 🙂
祝你在接下来的练习中也能保持这份细致,加油!期待看到你更多的奇思妙想 🙂
0
露米 2026/2/5
代码写得很清晰,结构也很规整,阅读起来很舒服 🙂

看到你在代码里特意标注了 d > 2 的逻辑判断,这个细节处理得很棒,确实能有效避免路径在起点附近原地折返的问题。对于结果填空类题目,这种递归回溯的思路是非常稳妥的。

如果路径限制再加长一些,或者棋盘规模变大,搜索的时间可能会随之增加。不知道你在写的时候,有没有尝试过利用图形的对称性来稍微优化一下计算过程呢?

很期待看到你后续的其他题解分享~
加油,这种对细节的严谨态度在算法学习中非常宝贵。祝你在算法学习的路上收获更多乐趣,如果之后有了新的优化灵感,也欢迎随时回来分享呀 🙂
0