标签: bfs

4 篇文章

Luogu P1225 黑白棋游戏 题解
Preface 题目链接 这题真的恶心,状压写错了调半天。。。 Description 给定一个 $4\times 4$ 的棋盘,每一格放一个棋子,共有 $8$ 个黑棋,$8$ 个白棋。每次可以交换相邻两个格子的棋子,问最少要多少步才能从初始状态到达最终状态。并且需要输出交换方法。 Solution 由于棋盘十分小(只有 $4\times 4$ )…
Luogu P4772 灰化肥,会挥发 题解
Description 在Farmer Justin的农场中有许多灰化肥,它们都堆积在A仓库里。为了方便施肥,Farmer Justin需要修一些公路使得他能用拖拉机把这些灰化肥拉到其他仓库里。由于Farmer Justin及其懒惰,所以他只想一次拉完所有的灰化肥送到其他仓库里。但是灰化肥见光易挥发,所以Farmer Justin需要尽快把这些灰化…
Luogu P2493 [SDOI2011]贪食蛇 & bzoj 2284. [Sdoi2011]贪食蛇 题解
Description 题目链接Luogu 题目链接bzoj 相信大家都玩过贪食蛇游戏,现在有一个改版贪食蛇游戏,跟传统的贪食蛇游戏一样,贪食蛇在活动区域内运动,吃食物,但是这个改版的贪食蛇游戏有着一些特别的规则。 活动区域: 贪食蛇的活动区域是一个R行C列的网格A,贪食蛇活动不能超过这个网格的范围。第i行第j列的方格用Ai,j表示。每个方格有一个…
bzoj3137 [Baltic2013]tracks 题解
Describe 给定一片长方形的草地,有2种动物:兔子和狐狸。兔子走过草地会留下R,狐狸走过草地会留下F。每只动物从左上角进入草地,从右下角走出草地。其间,它可以上下左右乱跳(可以重复),经过的格子会被覆盖上它的脚印。每次草地上最多只有一只动物。 给你地图,问最少有多少只动物走过了草地。 Solution 先将每一个边缘点加入$queue$,再每…