首页 > Luggage Lock
开通博客写题解
头像 Tsuku_Yomi_
发表于 2021-11-21 20:21:21
BFS 首先我们忽略起始数字，因为我们实际上可以把所有的起始数字转化为0000和密码转动起始数字 所以题目只有10000种输入（0000~9999） 考虑打表，开长度10000的表，由0000递推，每次转动一位，记录所需要转动到的最短的次数，总共有10种转动方法，求最短所以使用BFS 最后用一些方 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 lfzdsg
发表于 2021-11-22 10:12:55
题目： 转数字锁，每次选择相邻的加一位或减一位。然后给数字a, b问你用a最少次数转到b, 最少次数是多少 思路： 这里主要讲我的做法。赛时想到了对与每个数字，要么向前，要么想后，但是怎么交都是错的，赛后观察数据发现bug。对于每个数字，我们记录向前后向后的次数，然后由于只有4个数字，我们就可 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 杨瀚岚
发表于 2022-10-18 20:47:20
思路 我们可以将密码锁的每一个状态看成一个节点，每一个操作看成从一个节点到另一个节点的权重为1（意思是经过一次操作）的有向边，这个问题就可以看成一个最短路问题。 由于所有边的权重一致，我们可以使用bfs得出最短距离。 但问题是题目有T个测试集，有T个源点，可能互不相同，如果对每一个源点进行bfs会超 展开全文
去ta的博客 赞 (3) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”