下面我们来讲解 4655 瓷砖 这道题目。首先读入字符数组，找到小林的初始位置“ $a$ ”，并把坐标入队，作为队头元素。宽度优先搜索，检查队头元素的上、左、右四个位置是否是黑色瓷砖“.”，是则入队，·.....不断取出队头元素进行四个方向的拓展，直到队列为空。为了避免一个位置被多次重复走到，定义一个布尔型数组 $a[i,j]$ 用来判重，位置 $(i,j)$ 为黑色瓷砖设置为 $true$ ，红色的或者走过的瓷砖设置为 $false$。 最后，队列的尾指针即为答案。本题是搜索的一个重要应用，所谓的求“联通块”问题。

视频信息

答案文本 复制

视频字幕 复制

今天我们来讲解四六五五瓷砖问题。这是一道经典的连通块搜索问题。我们需要找到从起始位置a可达的黑色瓷砖组成的连通分量大小。我们将使用宽度优先搜索算法来解决这个问题。图中红色表示障碍物，白色表示可通行的黑色瓷砖，黄色表示起始位置。 现在我们详细讲解算法步骤。首先读入字符数组，找到起始位置a的坐标，这里是二二。然后初始化队列，将起始位置坐标入队。接着定义判重数组，布尔型数组用于标记访问状态，黑色瓷砖初始化为true，红色瓷砖初始化为false。 现在演示宽度优先搜索的具体过程。首先取出队头元素二二，然后检查它四个方向的相邻位置，分别是上下左右。将可通行且未访问的位置加入队列，同时标记当前位置为已访问。这样队列中就有了四个新的位置等待处理。 搜索过程继续进行，我们重复处理队列中的每个位置，对每个位置进行四方向扩展，直到队列为空。最终我们访问了九个黑色瓷砖位置，这些绿色标记的位置组成了一个连通块。根据题目描述，队列的尾指针就是答案，也就是连通块的大小等于九。 总结一下本题的关键要点。我们使用宽度优先搜索算法来求解连通块问题。通过队列进行广度优先遍历，使用判重数组避免重复访问同一位置。最终队列的尾指针就是连通块的大小。该算法的时间复杂度和空间复杂度都是O(mn)，其中m和n分别是网格的行数和列数。