*原题链接* T组测试数据，每组数据给定5x5的矩阵，求将其变为目标矩阵的最小步数。 做法：IDA* 分析：看到这样的数据范围和题目描述就可以想到搜索了，由于任何时候矩阵中只有一个空格，所以我们从空格开始进行搜索，看哪个骑士能转移到这个空格上。由于步数超过15步后输出-1，所以可以迭代加深搜索，但是这样爆搜后交上去会T，所以考虑如何优化。剪枝是剪不了的(至少我没想到哪里可以剪枝)，既然已经是

Description 　　在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑 士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空 位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步 数完成任务。 Input 　　第一行有一个正整数T(T<

Description 　　相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了 ，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字 表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图： 由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即

Description 在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。 Input 第一行有一个正整数T(T<

Problem: P2330 [SCOI2005] 繁忙的都市 文章目录 思路解题方法复杂度Code 思路 这是一道最小生成树（Minimum Spanning Tree）的问题。我们可以使用Kruskal算法来解决。 解题方法 首先，我们需要将所有的道路按照分值从小到大进行排序。然后，我们从分值最小的道路开始，依次判断这条道路的两个交叉路口是否已经连通。如果

从根开始dfs，用一个栈来维护目前还没有分配的点。对于当前处理的点，如果处理完一棵子树之后根的子树中剩下的节点达到 b b，就把这些点弹栈，这个根节点做省会。处理完子树之后把自己加入栈中。因为父亲节点一定比后继节点后入栈，而弹栈的时候会直接清空，也就是把所有后继节点都弹掉，所以不会出现断的情况。这样的话本来剩下的不到bb，从新子树中剩下的不到 b b，划分出来的省大小都不到2b2b。最后剩下的节点