P1047 校门外的树 Noip2005普及组第二题

P1047 校门外的树 是一道IT类问题，这是一道简单的模拟题，题目描述如下：

给定了一段道路的长度和一些树的位置，要求计算出这段道路上没有被树覆盖的长度。具体做法是先将树的位置记录在一个数组中，然后对数组进行排序，从而得到每两棵相邻树之间的空隙长度，将这些空隙长度累加起来即可得到未被覆盖的长度。如果第一棵树的位置不是0，则需要在0和第一棵树之间再计算一段长度。

相关问题

NOIP2008普及组第三题搜索

NOIP2008普及组第三题是搜索题目，题目描述如下：

在一个 4*4 的矩阵中，有 1-8 八个数字，其中有一个空位，可以与相邻的数字交换位置，现在给定一个初始状态和一个目标状态，问最少需要几步才能从初始状态到达目标状态。

输入格式：
输入包含两个 4*4 的矩阵，表示初始状态和目标状态，其中 0 表示空位。

输出格式：
输出一个整数，表示最少需要的步数。

输入样例：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

9 5 1 4
13 10 2 7
14 11 6 8
0 15 12 3

输出样例：
46

这道题可以使用广度优先搜索（BFS）的方法进行求解。

首先将初始状态和目标状态转化为字符串，并记录空位的位置。然后利用队列进行 BFS，每次从队首取出一个状态，枚举空位可以移动到的相邻位置，交换数字，得到新的状态，如果新状态等于目标状态，则返回步数，否则将新状态加入队列中。

代码实现如下：