如何从起点向外遍历未排序区域/体积？附数组遍历示例

嗨，针对你提出的从起点向外遍历未排序区域的需求，最适合的方法是广度优先搜索（BFS）——它天然是按「距离起点的层级」来逐层扩散遍历的，完美契合“向外”的遍历逻辑。下面结合你给出的4×3行优先数组来具体说明：

先明确基础对应关系 #

你的数组是4列（x范围0-3）、3行（y范围0-2），索引与坐标的转换公式为：
索引 = y * 4 + x
元素值等于索引，比如坐标(1,1)对应索引5，元素值就是5。

核心实现：BFS向外遍历 #

BFS的核心是用队列来管理待遍历的节点，配合一个访问标记数组避免重复访问。具体步骤如下：

1. 准备工作 #

• 定义方向数组：用来表示当前节点的上下左右四个相邻方向
• 初始化访问标记数组：记录哪些坐标已经被遍历过
• 初始化队列：将起点坐标加入队列，并标记为已访问

2. C++代码示例 #

假设我们选择坐标(1,1)（对应索引5）作为起点：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    const int cols = 4; // 列数
    const int rows = 3; // 行数
    int array[12];
    // 初始化数组，元素值等于索引
    for (int i = 0; i < 12; ++i) {
        array[i] = i;
    }

    // 起点坐标 (y, x) = (1,1)，对应索引5
    int start_y = 1;
    int start_x = 1;

    // 方向数组：上下左右四个方向
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    // 访问标记数组，初始全为false
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    // 队列存储坐标对 (y, x)
    queue<pair<int, int>> q;

    // 初始化队列和访问标记
    q.push({start_y, start_x});
    visited[start_y][start_x] = true;

    cout << "从起点(1,1)向外遍历的结果：";
    while (!q.empty()) {
        // 取出队首节点
        auto curr = q.front();
        q.pop();
        int y = curr.first;
        int x = curr.second;
        // 输出对应元素值
        cout << array[y * cols + x] << ",";

        // 遍历四个方向的相邻节点
        for (auto& dir : dirs) {
            int new_y = y + dir[0];
            int new_x = x + dir[1];
            // 检查新坐标是否在数组范围内，且未被访问过
            if (new_y >= 0 && new_y < rows && new_x >=0 && new_x < cols && !visited[new_y][new_x]) {
                visited[new_y][new_x] = true;
                q.push({new_y, new_x});
            }
        }
    }
    cout << endl;
    return 0;
}

3. 遍历结果说明 #

运行这段代码，输出会是：5,1,9,4,6,0,2,8,10,3,7,11,
对应的遍历层级是：

• 第1层（起点）：5
• 第2层（起点相邻节点）：1、9、4、6
• 第3层（第二层节点的相邻未访问节点）：0、2、8、10
• 第4层（第三层节点的相邻未访问节点）：3、7、11

完全是从起点逐层向外扩散的顺序。

扩展到三维体积遍历 #

如果是三维体积的遍历，思路完全一致：

• 方向数组扩展为6个（上下左右前后）
• 坐标变为三维(x,y,z)，索引转换公式调整为索引 = z * rows * cols + y * cols + x
• 访问标记数组也变为三维的

这种方法的优势在于，不管数组是有序还是无序，都能保证从起点开始，按距离由近及远遍历所有未访问区域，非常适合区域探索、填充类的场景。

内容的提问来源于stack exchange，提问作者Mr. Smith