不知道怎么写

我们面对的是一个提交答案题，题目要求构造一个迷宫，使得迷宫中的空格形成一棵树（任意两个空格之间有且仅有一条简单路径），并且在这个迷宫中，能够躲藏的小孩（即度数为1的空格节点）尽可能多。小孩只能躲藏在度数为1的空格上（即恰好有一个邻居是空格），每个这样的空格只能躲藏一个小孩。

注意：输入是一个网格图，包含空格 '.' 和岩石 '#'。输出中可以将一些空格 '.' 变成 'X'（表示种植灌木），但不能改变岩石 '#'，也不能在岩石上种植灌木。

条件：

输出的地图中，除了将输入中的一些 '.' 变成 'X' 外，其他部分不变。
迷宫性质：所有剩余的空格（即未被岩石和灌木占据的格子）构成的图是一棵树（任意两个空格有且仅有一条简单路径）。
目标：最大化度数为1的空格节点（即叶子节点）的数量。

评分：对于每个测试点，给定k，如果我们构造的迷宫有l个叶子节点，则得分为 min(10, 10*l/k)（向下取整到小数点后两位）。如果输出无效（即不满足上述两个条件），则得0分。

策略： 由于我们需要构造的迷宫是一棵树，那么树中叶子节点的数量是我们要最大化的目标。在一棵树中，叶子节点的数量可以通过以下方式估计： 设节点总数为V，边数为V-1。 根据握手定理：所有节点的度数之和等于2*(V-1)。 设叶子节点（度数为1）有l个，其他节点（度数>=2）有V-l个，则有： l + 2*(V-l) >= 2*(V-1) [因为非叶子节点的度数至少为2] 整理得：l >= 2 事实上，更精确的公式是：l = 2 + sum_{i>=2} (度数-2) [由2E = sum deg = l + sum_{非叶子} deg 和 E=V-1 推导] 但是，我们也可以知道，叶子节点的数量至少为2（除非只有一个节点，但一个节点时叶子节点为1，但这里我们通常有多个节点）。

然而，我们想要最大化l。在树中，叶子节点的数量并没有固定的上限，但受限于网格的结构。

但是，我们受到网格的限制：空格原本是连通的吗？题目没有保证初始连通，但我们的迷宫必须是连通的（树是连通的）。因此，我们只能选择网格的一个连通子图作为树，并且要求这棵树没有环（树的性质）。

注意：我们只能将空格变成灌木，不能改变岩石。初始时，空格点可能形成多个连通块，但我们可以选择其中一个连通块来形成树（因为树必须是连通的，所以不能跨越多个连通块），而将其他连通块的空格全部变成灌木（即X）？但是，题目要求迷宫必须满足任意两个空格之间有唯一路径，这意味着整个迷宫的空格必须连通且无环。所以，我们只能保留一个连通块，并且将这个连通块修剪成一棵树（即去掉一些边形成树，也就是将一些格点变成灌木来断开环）。

因此，我们的步骤是：

选择网格中的一个连通块（通常选择最大的连通块，因为节点数多，可能产生更多的叶子）。
在这个连通块中，生成一棵生成树，并且希望这棵生成树的叶子节点尽可能多。
如何生成一棵叶子尽可能多的树？ 注意：在树中，叶子节点的数量 = 2 + sum_{非叶子节点} (度数-2) 因此，为了最大化叶子节点，我们希望非叶子节点的度数尽可能接近于2（即尽量形成一条链状结构，避免分叉，因为分叉会导致非叶子节点的度数增加，从而减少叶子节点数？不对，看公式：每个非叶子节点的度数大于等于2，那么(度数-2)为非负数，所以非叶子节点的度数增加实际上会使得叶子节点数增加？不对，让我们重新思考：

公式：设所有节点的度数和为2E=2(V-1)，又设叶子节点数为l，非叶子节点数为V-l，每个非叶子节点的度数至少为2，那么： l * 1 + (V-l) * d_min <= 2(V-1) -> 这里d_min=2 l + 2(V-l) <= 2(V-1) => l + 2V - 2l <= 2V - 2 => -l <= -2 => l>=2

这个不等式只给出了下界，但是并没有直接给出如何最大化l。

换一个角度：在树中，叶子节点的数量等于所有节点的度数中1的个数。而度数序列必须满足：所有节点的度数之和为2(V-1)，并且度数序列是正整数，且至少两个节点的度数为1（V>=2时）。

我们可以尝试构造：如果我们构造的树是一条链，那么叶子节点只有两个（链的两端）。如果我们希望叶子节点多，那么树应该尽可能“发散”，即像星型树那样？实际上，星型树（一个中心节点，其他节点都是叶子）有V-1个叶子节点。

结论：树中叶子节点的数量范围是[2, V]（当V>=2时）。当树为星型树时，叶子节点数最多，为V-1（中心节点不是叶子）。

因此，我们的目标是：在选定的连通块中，构造一棵星型树（即一个中心节点，其余节点都与中心直接相连）？但是，网格图的限制：两个节点相邻必须是邻居（上下左右），所以星型树要求中心节点与所有其他节点都是邻居，这通常是不可能的（除非连通块是一个星型结构，且中心与所有点相邻）。

实际上，在网格图中，一个节点最多有4个邻居。因此，中心节点的度数最多为4，那么星型树最多只能有4个叶子节点。这样叶子节点数最多为4？这显然不是最大的，因为我们可以构造多级结构。

重新审视公式：叶子节点数 l = 2 + sum_{非叶子节点} (度数-2) 如果我们让非叶子节点的度数尽可能大，那么每个非叶子节点对叶子节点数的贡献（度数-2）就大，从而叶子节点数就大。因此，我们希望非叶子节点的度数尽可能大（即度数大于等于3的节点越多越好，并且度数尽量大）。

例如：一个节点度数为3，则贡献1；度数为4，则贡献2；等等。 那么，我们可以在树中构造多个度数较高的节点。在网格图中，一个节点的度数最大为4，所以每个非叶子节点的最大贡献为2（当度数为4时）。

如果我们有h3个度数为3的节点，h4个度数为4的节点，那么叶子节点数 l = 2 + h3 + 2*h4。

因此，为了最大化l，我们应在树中尽可能多地构造度数为4的节点（即十字交叉点），其次是度数为3的节点（T型交点）。

但是，网格图的连通性限制了节点的度数：一个节点最多有4个邻居，且树中节点的度数不能超过4。

因此，我们的目标是在给定的网格连通块中，构造一棵生成树，使得度数为3和4的节点尽可能多。

具体构造方法： 我们可以将问题转化为：在连通块中，我们选择一棵生成树，使得非叶子节点中度数大于2的节点尽可能多（且度数尽量大）。注意，我们并不是真的在图上添加边，而是通过删除一些节点（变成灌木）来断开环，同时保持连通（树）。

然而，直接最大化叶子节点数（即度数为1的节点）是一个困难的问题（可能是NP-hard的）。但是，题目中网格尺寸最大为1024x1024，节点数最多约10^6，所以我们不能使用指数算法。

但是，注意这是提交答案题，我们可以针对每个测试数据单独设计构造算法，或者使用启发式算法。

常见的构造思路：

深度优先搜索（DFS）树：在DFS树中，非树边全部去掉（即产生环的边用灌木隔开）。DFS树通常会产生很多叶子节点，因为DFS倾向于走一条路径，然后回溯较少，所以分支不会太多，叶子节点数可能不够多。
广度优先搜索（BFS）树：类似。
最小生成树（MST）：这里没有边权，我们可以考虑最大叶子生成树（Maximum Leaf Spanning Tree）。最大叶子生成树问题就是寻找一棵生成树，使得叶子节点最多。但是，这是NP-hard问题，但我们可以用启发式算法。
启发式算法：

贪心：从一个点开始，每次将叶子节点的邻居加入树（类似BFS），但这样会形成一条链，叶子节点很少。

另一种贪心：选择最长的路径（直径）作为主干，然后尽可能多地让其他节点作为叶子节点挂到主干上。具体步骤如下： a. 在连通块中，选择两个距离最远的节点作为主干的两端（直径）。 b. 沿着直径，我们将直径上的节点作为非叶子节点（这些节点度数至少为2，因为要连接前后）。 c. 对于不在直径上的节点，我们将其连接到主干上：从每个节点出发，寻找一条到主干的路径（尽量短），然后将该路径与主干连接。这样，该节点就会成为主干上某个节点的邻居，从而增加主干上节点的度数，同时该节点本身成为叶子（如果它不再延伸）或者成为分支节点。 d. 但是，这样构造可能导致主干上的节点度数增加（最多4），而分支上的节点如果只连接一次，则它们就是叶子。

这样，叶子节点包括： - 直径的两个端点（如果它们没有分支则成为叶子，但如果有分支则可能度数大于1，所以不一定） - 所有分支的末端节点（即不在主干上的节点，如果它们只与主干连接，则成为叶子）

注意：在网格图中，一个节点最多有4个邻居，所以主干上的一个节点最多可以连接3个分支（因为主干上已经有两个邻居，左右各一个，所以最多再连接两个分支，否则度数会超过4？实际上，我们在构造树，度数可以超过4？不行，因为树中节点的度数在图的度数上不会超过4（网格每个点最多4个邻居）。所以我们最多只能连接两个分支。

因此，主干上的节点最多可以挂两个叶子（分支）。这样，叶子节点的数量大约是（分支节点数）*1（每个分支的末端叶子） + 直径的两个端点（如果它们没有分支则算两个）？但有可能分支本身就比较长，分支上也可以再挂分支？这样分支上的节点也可能成为非叶子节点，从而减少叶子节点数。

因此，我们更希望分支尽可能短，即直接从主干一步到达分支的末端（这样分支上的节点就是叶子）。这样，每个分支只占用主干节点的一个度数，同时增加一个叶子节点。

但注意：我们构造的是树，所以不能有环。我们只需保证每个不在主干上的节点通过一条路径连接到主干，然后将这条路径上除了与主干连接的那个节点外，其余节点都可以作为叶子节点？不对，因为路径上除了与主干连接的那个节点外，其他节点如果只有一个分支（即路径上的下一个节点），那么它们也是叶子节点（路径末端）？实际上，从主干出发的分支路径上，只有最末端的节点是叶子，而路径中间节点都有两个邻居（前一个和后一个），所以度数至少为2，因此不是叶子。

所以，如果我们用一条长度为L的分支路径，那么这条路径上只有末端节点是叶子，而其他节点都不是叶子。这样，我们用L个节点只产生了一个叶子。这效率不高。

另一种思路：尽可能让分支长度短，最好是1。即分支节点直接连接到主干节点。这样，每个分支节点就是一个叶子节点（因为它只与主干节点相连，没有其他邻居）。这样，我们用1个节点就产生1个叶子节点。因此，我们希望尽可能多地将节点作为分支直接连接到主干上。

但是，主干节点的度数有限制：一个主干节点最多只能连接两个分支（因为主干节点在主干上已经有两个邻居了，再连两个分支，度数刚好为4）。这样，如果我们有长度为L的主干，那么主干上最多可以挂的点数是2L（每个主干节点挂两个分支）。而整个树的节点数就是主干节点数（L）加上分支节点数（2L），即3L。而叶子节点数：分支节点都是叶子（2*L个），主干上除了两端点外，中间节点因为度数至少为2（主干前后两个连接）再加上分支（至少一个分支，所以度数>=3），所以主干中间节点不是叶子；主干端点：如果端点没有分支（但实际上我们希望尽可能给端点也挂分支），但是端点在主干上只有一个邻居（另一个是空），所以端点可以挂两个分支（这样端点度数就是1（主干方向）+2（两个分支）=3？不对，主干端点只有主干方向一个邻居，所以可以挂最多3个分支？但网格限制最多4个邻居，所以最多挂3个分支？不对，端点最多有4个邻居，但其中一个已经被主干上的下一个节点占用（如果主干长度>=2，则端点有一个邻居是主干上的相邻节点，另外三个邻居可以挂分支）。因此，端点可以挂3个分支。

因此，叶子节点数 = 分支节点数（每个分支节点都是叶子）+ 主干端点（如果某个主干端点没有连接分支，则它是叶子，但如果有分支则不是叶子）？不对，主干端点如果连接了分支，则它的度数大于1，所以不是叶子。所以叶子节点就是所有的分支节点（直接挂在主干上的节点）。

那么，叶子节点数 = 分支节点数 = 每个主干节点可以挂的分支数之和。

因此，我们最大化分支节点数：每个主干节点最多可以挂的分支数 = 4 - 主干上的度数（主干中间节点有两个主干邻居，所以最多挂2个分支；端点有一个主干邻居，最多挂3个分支）。

因此，叶子节点数最大为：设主干长度为L，则中间节点有L-2个，每个挂2个分支；两个端点，每个挂3个分支。则总叶子节点数 = 2*3 + (L-2)*2 = 2L+2。

而总结点数V = L（主干） + (2L+2)（分支） = 3L+2。所以叶子节点数大约是总节点数的2/3。

但是，我们不一定能挂满，因为网格中可能没有那么多相邻的分支节点可用（即主干节点的邻居可能被岩石占据，或者本身就是岩石而不能挂分支）。

因此，具体步骤：

选择连通块：通常选择最大的连通块。

找到连通块的直径（最长路径）：使用两次BFS。

将直径作为主干。

对于不在主干上的节点，我们尝试将其直接连接到主干节点（即成为主干节点的邻居）。连接的条件是这个节点是空格，并且与主干节点相邻，并且该连接不会产生冲突（每个主干节点最多挂2个（中间节点）或3个（端点）分支节点）。注意，我们只能连接连通块内的空格。

但是，这样处理之后，可能还有一些节点没有被连接到主干（因为主干节点的邻居不够或者位置不够）。对于这些节点，我们可以考虑将它们连接到分支节点上？但是这样分支节点就不是叶子了（因为分支节点有了邻居），所以我们不这样做，因为我们希望分支节点必须是叶子（度数1）。如果某个节点不能直接连接到主干，我们就将其设置为灌木（即放弃这个节点，变成X），以保证我们的树只包含主干和直接挂在主干上的叶子。

最后，我们还需要检查整个树是否连通（应该连通，因为我们只保留主干和直接挂在主干上的节点，而这些节点都是通过主干连接的），并且无环（因为我们每次添加节点都是直接挂到主干上，没有连接两个主干节点，所以不会形成环）。

但是，这个方法可能会丢弃很多节点（因为不能挂到主干上的节点会被变成灌木），导致总节点数减少，从而叶子节点数也可能减少。我们是否可以不丢弃这些节点，而是用较长的分支连接？但前面分析，较长的分支会减少叶子节点数。

另一种权衡：我们希望保留更多的节点，即使需要一些较长的分支。例如，如果我们允许分支长度为2，那么一个分支需要两个节点，产生一个叶子节点（末端节点）和一个非叶子节点（分支与主干连接处）。这样，两个节点产生一个叶子节点。而如果丢弃这两个节点，则叶子节点为0。所以，我们选择保留，至少得到一个叶子节点。同样，分支长度为3时，三个节点产生一个叶子节点。

因此，如果我们有额外节点，我们可以通过形成分支路径来将它们挂到主干上，但这样效率较低（一个分支路径上只有末端节点是叶子）。所以，优先使用直接连接（分支长度为1），然后再考虑使用较长分支。

但是，使用较长分支会占用中间节点的度数（这些中间节点成为非叶子节点，度数至少为2），而且这些中间节点可能还可以挂其他分支？如果中间节点有多余的度数，就可以挂其他分支（即分支上再分支），这样中间节点也可以产生新的叶子节点。

为了最大化叶子节点，我们应当尽量利用节点的度数（达到4），这样每个非叶子节点可以连接尽可能多的分支。

因此，我们设计一个贪心过程：

选择主干（最长路径）。
将主干上的节点标记为属于主干。
初始化一个队列，将所有不在主干上但与主干相邻的节点加入队列（作为第一层分支）。
然后进行BFS：从队列中取出一个节点u，将它连接到主干（或者其他已经连接到树的节点v）上，要求v是已经加入树的节点且u与v相邻。连接操作：标记u的父节点为v（在树中），并将u加入树（保留为空格）。然后，对于u的邻居（不在树中的空格），如果它们没有被访问过，则加入队列。
注意：每个节点的度数不能超过4（网格限制，但树中节点的度数在网格图中实际不会超过4，因为邻居只有4个）。我们在添加邻居时，要确保添加后度数不超过4。但是，在树中，一个节点可以连接的子节点数最多为3（因为父节点已经占一个邻居，所以最多3个子节点）。
但是，这样构造的树，叶子节点就是所有没有子节点的节点（即树中的叶子）。我们希望叶子节点尽可能多，那么我们应当避免节点有多个子节点？不对，我们希望节点尽可能多地扩展子节点（因为一个节点最多3个子节点，这样树会更宽，叶子节点也会更多）。实际上，完全四叉树（每个节点最多4个孩子，但网格中每个节点最多有4个邻居，所以树中每个节点最多3个孩子，因为有一个邻居要留给父节点）的叶子节点数量大约是总节点数的一半？不对，完全二叉树有n个节点，叶子节点数大约是n/2，完全三叉树叶子节点比例更高。实际上，在树中，叶子节点数 = 1 + sum_{非叶子节点}(孩子数-1)。因此，我们希望非叶子节点的孩子数尽可能多（但不能超过3）。

因此，我们使用BFS扩展树，每次一个节点可以连接最多3个子节点（即除了父节点外的邻居中最多3个空格）。这样，树会尽可能宽，从而产生更多的叶子节点。

具体步骤：

选择根节点：选择直径的一个端点作为根。
从根开始进行BFS，在遍历过程中建立树。在遍历时，我们按照BFS的顺序将节点加入树，每个节点加入树时，它的父节点已经确定（即BFS中扩展出它的节点），然后它最多可以再扩展3个子节点（即除了父节点外，它还有3个邻居可以扩展）。
这样，叶子节点就是那些在BFS队列中无法再扩展（即没有未访问邻居）的节点。
但是，这样构造的树，叶子节点数是否足够多？实际上，在BFS树中，叶子节点数量取决于树的结构。在完全三叉树（每个节点三个孩子）中，叶子节点数 = 1 + 3 + 3^2 + ... + 3^(h-1) 在最后一层，叶子节点数约为3^{h，而总节点数约为(3}h-1)/2，所以比例约为2/3。而链状树则叶子节点只有2个。

因此，BFS树（宽度优先）可以产生很多叶子节点。但是，我们初始的根节点选择很重要，我们希望树尽可能宽。

另一种方法：随机选择根节点，多次运行取叶子节点最多的树？但网格较大，多次运行不可行。

因此，我们选择直径的端点作为根，这样树可能会更深，但直径端点的选择有助于树的扩展更加平衡。

然而，我们必须在构造树的过程中确保每个节点的度数不超过网格的限制（即最多4个邻居，但在树中，每个节点的度数（邻居数）不能超过4，因为我们不能在一个节点上连接超过4个邻居）。在树中，一个节点的度数就是它在树中的边的数量，而树中边的数量就是它的孩子数+1（父节点）。所以，每个节点的孩子数最多为3。

算法步骤：

读入网格图。

找出所有空格（'.'）组成的连通块，选择最大的连通块。

在连通块中，用两次BFS计算直径（选择一个点S，BFS找到最远的点T；再从T开始BFS找到最远的点U，则T->U是一条直径）。

以T（或U）为根，运行BFS（建立树），同时记录每个节点的父节点。 具体做法： queue Q 将根节点加入队列，标记访问，深度=0。 while Q非空： 取出队首节点u 遍历u的四个邻居v（上下左右）： 如果v是空格（在连通块内）且未被访问，则： 将v的父节点设为u 将v加入队列 标记访问v 将v的坐标加入树（保留为空格） 然后将u的孩子数加1 注意：如果u的孩子数已经达到3（即除了父节点外，已经连接了3个孩子），则u不能再扩展其他邻居（跳过u的其他邻居）？不对，我们还是要扩展其他邻居，因为u可能有多个邻居需要处理，但u只能连接3个孩子（因为父节点占一个位置，所以最多3个孩子）。所以，当u的孩子数达到3时，我们就不再处理u的其他邻居了吗？不，我们仍然要处理，因为其他邻居可能由其他节点扩展（即u的邻居可能由u的父节点或兄弟节点扩展）。

所以，我们不应该跳过，而是继续处理u的邻居，即使u已经达到3个孩子，因为其他邻居可能被其他节点访问。

但是，这样构造的树可能不是最优的（叶子节点不够多），因为我们没有控制节点的扩展顺序。为了尽可能多地产生叶子节点，我们应该优先扩展度数较小的节点？不对，我们更希望先扩展节点，使得树更宽。所以BFS本身就是按层扩展，使得树比较宽。

最后，所有在连通块内但没有被访问的节点（因为我们只从根开始BFS，并且连通块是连通的，所以应该都能访问到？）然后，我们将不在树中的空格（连通块中剩余的空格）都变成灌木（X）。实际上，我们不需要这样做，因为我们的树已经包含了整个连通块（因为我们遍历了整个连通块）？不对，我们遍历了整个连通块，所以所有连通块内的节点都被访问了，并且加入了树。所以，我们不需要将任何节点变成灌木？不对，因为我们建立的树可能要求节点不能有额外的边（否则会形成环），所以我们必须将一些空格变成灌木来断开环。但是，在我们的BFS树中，我们只保留了树边，而其他的边（非树边）对应的节点并没有被断开？不对，我们在建立树时，每个节点只被访问一次，并且只通过一条边连接到树，所以不会形成环。

然而，问题在于：网格图中，两个节点之间可能存在多个路径（环），而我们在BFS树中只保留树边，那么其他边对应的网格连接并没有被破坏（即两个节点在网格中相邻，但在树中不一定相邻，所以不会形成环？不对，树中已经规定了两点之间的路径唯一，但是网格图中两个节点可能既是树边又是非树边？不对，我们在BFS树中，每个节点只有一个父节点，所以不会形成环。因此，整个树是连通的，而且没有环。所以，我们不需要再添加任何灌木？不对，网格图中，两个节点可能有多个边（即网格中的邻居关系）？但是，在树中，两个节点之间只有一条路径，而网格图中的邻居关系并不会自动形成边。我们构造的树是基于网格图的，树中的边就是网格中的相邻关系。所以，只要我们在树中没有使用某个邻居关系，那么这两个节点在树中就不是直接相连的，所以不会形成环。因此，整个空格集合已经构成了一棵树。

但是，我们并没有将非树边对应的空格变成灌木。注意：在网格图中，两个节点相邻不代表它们在树中相邻。在树中，两个节点可能不相邻（即网格中不相邻？不一定，网格中相邻但在树中可能不是父子关系）。所以，原本网格图中相邻的两个节点，在树中可能不是直接相连的，那么这两个节点在树中的路径长度大于1，所以没有问题（唯一路径）。因此，我们不需要额外添加灌木来断开非树边？因为非树边并不存在于树中，所以不会形成环。树的结构已经保证了唯一路径。

然而，问题在于：网格图的原始连接是存在的，但我们的树只使用了部分连接。树中，两点之间的唯一路径就是树路径，而网格图中其他存在的边（非树边）并没有被破坏。但是，题目要求的是：在迷宫中，任意两个空格之间只能有唯一一条简单路径。如果存在非树边，那么两个节点之间就有两条路径：一条是树路径，另一条是通过非树边的路径。所以，我们必须破坏非树边？破坏非树边的方法：将非树边对应的两个节点中的一个节点变成灌木，或者将非树边对应的网格位置断开？但是，非树边对应的两个节点都是空格，我们并没有断开。

所以，我们必须确保：在树中没有使用的边（即非树边）不能连接两个空格。也就是说，如果两个节点在网格中相邻，但它们在树中不是父子关系，那么这两个节点之间不能同时保留为空格。所以，我们需要将其中至少一个节点变成灌木？或者两个都保留，但这样就会形成环。

因此，我们的BFS树构造后，需要将连通块中所有不在树上的空格变成灌木？不对，我们的树已经包含了整个连通块，并且树中没有使用的边（网格中的边）不会在树中形成连接，因为树已经覆盖了所有节点。但是，例如：节点A和节点B在网格中相邻，在树中A是B的父节点（树边），所以没问题。节点A和节点C在网格中相邻，但在树中，A和C不是父子关系（比如C是B的子节点），那么A和C相邻就会形成环（A->B->C和A-C构成环）。所以，我们必须破坏非树边。

解决方法：将非树边对应的两个节点中的一个节点变成灌木？或者将非树边对应的两个节点之间的连接断开？但网格图中断开连接只能通过将节点变成灌木（因为不能改变岩石，也不能添加灌木到边上，只能添加到节点上）。所以，我们必须将非树边的一个端点变成灌木。但是这样就会破坏树的结构（因为树中包含这个节点）。

因此，我们必须在构造树的过程中避免非树边？不可能，因为树中只有n-1条边，而网格图中连通块内的边数可能大于n-1。所以，我们必须将一些节点变成灌木来断开非树边。

重新思考：题目要求，输出中只能将空格变成灌木，不能改变岩石。构造迷宫后，剩余的空格必须形成一棵树（即任意两点有唯一路径）。所以，我们必须破坏所有的环。破坏环的方法：保留一个生成树，然后将其他所有边断开。断开边的方法：将非树边对应的两个节点中，至少一个节点变成灌木，或者将非树边对应的两个节点之间的所有路径断开（但网格图中相邻的节点，断开只能通过将节点变成灌木）。

因此，我们有两种策略： (1) 保留一棵生成树，然后对于每一条非树边，将其中一个节点变成灌木。但这样可能破坏树的结构（因为非树边涉及的节点可能被破坏），而且可能破坏很多节点。 (2) 在构造生成树之后，将不在树中的节点全部变成灌木？这样，剩下的节点就是树中的节点，并且树中相邻的节点在网格中相邻（因为树边是网格中的边），而非树边对应的两个节点至少有一个不在树中（被删除了），所以非树边就不存在了。这样，树中的节点之间只有树边，所以没有环。

策略(2)更直接：我们只保留树中的节点，而将连通块中其他节点都变成灌木。这样，树中的边都是网格中相邻的，且没有非树边（因为不在树中的节点被删除了，所以非树边的一个端点不存在了）。