Posts tagged with BFS


第一次刷到HDU第一名,趁现在没人比我高,截图来一发!!!! 对于这道题,我只想说一个字 妙!!!! 题意: 给你四个点,(1,2),(2,3),(3,4),(4,1)之间都有一条无向路径,让你从 2 号点出发,最后回到2号点,同时使得走过的距离大于等于 k ,并且 最小。…

bfs + dp 好题。 真好,比赛的时候想不出来,看题解的时候感觉好复杂…… 看完写的时候感觉非常流畅! 题意: 载人过岸,一艘船最大载重 k 已经给定。每个人的重量只会是50或者100。问最小的过岸次数与方案数。 思路: 老实说这个题目我可以看就知道是道搜索题,因为和那个什么东西(就是搜索入门的那个)来着非常像。 最重要的还是理清状态与思路。 以左岸50重人数,100重人数,船是否在左岸表示一个状态,对他进行 bfs…

康复计划之搜索 1 因为有个小学弟在第二天就说ida * 看不懂,搞得我挺慌 我可以说我也不是很熟么 题意: 经典八数码 思路: 这里提供的是单向bfs + 打表思路,本来想复习ida * 但是不小心看到了kuangbin的思路,就写了一下。 简单说就是我从起始状态 123456780 开始对0进行bfs,通过康托展开的hash函数进行记录状态和路径。询问时对哈希值进行询问和查找。 实际上并没有用到康托展开的性质,只是通过2进制hash而已…… #include <algorithm>…

白书训练指南上的第一道基础题,因为它在搜索中引入了超级源点,所以我自己试着做了一下,真的宛如发现新大陆一般,图论的建图技巧真的是在整个图论领域都十分适用啊。 因为UVa的尿性,写完去搜一下题解,居然有很多题解都是两次 bfs ……真是笑了 题意: 一个起火的迷宫,有很多起火的地点,给你初始位置,和起火地点,你的逃跑速度和火焰蔓延速度相等,问你能否跑出迷宫,若能,输出最短时间。 思路: 网上那些两遍bfs的应该是先一遍bfs处理出火焰蔓延到每一个格子的最短时间,在自己bfs时间加个时间大小判断的限制。 然而实际上,我们溶入超级源点的思路,然所有点一起开始跑,…

稍微有点不一样 这次衡量的第一标准是位数的多少 第二标准才是数的大小 这里必须有一个 数论的 知识 不然不好写(I hate number theroy …… 对于任意的整数n,必然存在一个由不多于两个的数来组成的一个倍数。(之前写过数位BFS的应该可以理解 因为a,aa,aaa……取n+1个,则必有两个模n余数相同,相减即得n的倍数m。而m只由a、0组成。(这可以说是最糟的情况 所以只要先枚举所有的…