泛洪算法专题

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0

从(2,2)开始泛洪填充为2:

0 0 0 0 0
0 1 1 1 0
0 1 2 1 0
0 1 1 1 0
0 0 0 0 0
继续扩散:
0 0 0 0 0
0 1 2 1 0
0 2 2 2 0
0 1 2 1 0
0 0 0 0 0
最终结果:
0 0 0 0 0
0 1 2 1 0
0 2 2 2 0
0 1 2 1 0
0 0 0 0 0

function floodFill(grid, x, y, oldColor, newColor):
    if x < 0 or x >= grid.width or y < 0 or y >= grid.height:
        return  // 超出边界
    
    if grid[x][y] != oldColor:
        return  // 不是目标颜色
    
    grid[x][y] = newColor  // 填充新颜色
    
    // 递归处理四个方向
    floodFill(grid, x+1, y, oldColor, newColor)  // 右
    floodFill(grid, x-1, y, oldColor, newColor)  // 左
    floodFill(grid, x, y+1, oldColor, newColor)  // 下
    floodFill(grid, x, y-1, oldColor, newColor)  // 上

泛洪算法的关键点：

• 起始条件：选择合适的起始点
• 扩散条件：定义何时继续扩散
• 终止条件：确定何时停止扩散
• 访问标记：避免重复访问同一点
• 边界检查：防止越界访问

泛洪算法的变种：

• 4-连通泛洪：只考虑上下左右四个方向
• 8-连通泛洪：考虑包括对角线在内的八个方向
• 条件泛洪：根据特定条件决定是否扩散
• 多源泛洪：从多个起始点同时开始扩散

DFS实现泛洪的代码框架：

void floodFillDFS(vector<vector<int>>& grid, 
                 int x, int y, 
                 int oldColor, int newColor) {
    // 边界检查
    if (x < 0 || x >= grid.size() || 
        y < 0 || y >= grid[0].size()) {
        return;
    }
    
    // 检查是否是目标颜色
    if (grid[x][y] != oldColor) {
        return;
    }
    
    // 填充新颜色
    grid[x][y] = newColor;
    
    // 递归处理四个方向
    floodFillDFS(grid, x+1, y, oldColor, newColor);
    floodFillDFS(grid, x-1, y, oldColor, newColor);
    floodFillDFS(grid, x, y+1, oldColor, newColor);
    floodFillDFS(grid, x, y-1, oldColor, newColor);
}

BFS实现泛洪的代码框架：

void floodFillBFS(vector<vector<int>>& grid, 
                 int x, int y, 
                 int oldColor, int newColor) {
    // 边界检查和初始颜色检查
    if (x < 0 || x >= grid.size() || 
        y < 0 || y >= grid[0].size() || 
        grid[x][y] != oldColor) {
        return;
    }
    
    // 方向数组
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    
    queue<pair<int, int>> q;
    q.push({x, y});
    grid[x][y] = newColor;  // 标记起始点
    
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        
        // 检查四个方向
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            // 边界检查和颜色检查
            if (nx >= 0 && nx < grid.size() && 
                ny >= 0 && ny < grid[0].size() && 
                grid[nx][ny] == oldColor) {
                grid[nx][ny] = newColor;
                q.push({nx, ny});
            }
        }
    }
}

• 常见应用场景的复杂度：
  1. 图像填充：
     • 时间：，和是图像的宽和高
     • 空间：，需要标记已访问的像素
  2. 连通区域标记：
     • 时间：，是区域内的点数
     • 空间：，最坏情况下需要存储所有点
  3. 迷宫探索：
     • 时间：，和是迷宫的行数和列数
     • 空间：，需要标记已访问的格子

// 上、右、下、左四个方向
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// 使用方向数组
for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    // 处理新位置(nx, ny)
}

// 8个方向（包括对角线）
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

// 使用方向数组
for (int i = 0; i < 8; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    // 处理新位置(nx, ny)
}

自定义方向：

// 国际象棋中马的移动方向
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

// 使用方向数组
for (int i = 0; i < 8; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    // 处理新位置(nx, ny)
}

方向数组的优势：

• 代码更加简洁
• 避免重复编写相似的代码
• 易于扩展和修改移动方向
• 可以根据需要自定义不同的移动模式
• 结合循环使用，提高代码可读性

注意事项：

• 确保方向数组的长度与使用时的循环范围一致
• 在使用新位置前进行边界检查
• 根据问题特点选择合适的方向集合

int countIslands(vector<vector<int>>& grid) {
    if (grid.empty()) return 0;
    
    int rows = grid.size();
    int cols = grid[0].size();
    int count = 0;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) { // 陆地
                count++; // 发现新岛屿
                // 使用泛洪算法将整个岛屿标记为已访问
                floodFill(grid, i, j, 1, 0);
            }
        }
    }
    
    return count;
}

void floodFill(vector<vector<int>>& grid, int x, int y, 
               int land, int visited) {
    if (x < 0 || x >= grid.size() || 
        y < 0 || y >= grid[0].size() || 
        grid[x][y] != land) {
        return;
    }
    
    grid[x][y] = visited; // 标记为已访问
    
    // 递归处理四个方向
    floodFill(grid, x+1, y, land, visited);
    floodFill(grid, x-1, y, land, visited);
    floodFill(grid, x, y+1, land, visited);
    floodFill(grid, x, y-1, land, visited);
}

区域分割：

• 将图像或网格分割成不同的连通区域
• 每个区域具有相似的特性（如颜色、纹理）
• 用于图像分析、计算机视觉和模式识别
• 可以为每个区域分配唯一标识符

实现示例：

void segmentRegions(vector<vector<int>>& image) {
    int rows = image.size();
    int cols = image[0].size();
    int regionId = 2; // 从2开始标记区域（假设0和1有特殊含义）
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (image[i][j] == 1) { // 未标记的区域
                // 使用泛洪算法标记整个区域
                labelRegion(image, i, j, 1, regionId);
                regionId++; // 下一个区域使用新的标识符
            }
        }
    }
}

void labelRegion(vector<vector<int>>& image, int x, int y, 
                int oldLabel, int newLabel) {
    if (x < 0 || x >= image.size() || 
        y < 0 || y >= image[0].size() || 
        image[x][y] != oldLabel) {
        return;
    }
    
    image[x][y] = newLabel; // 标记为新区域
    
    // 递归处理四个方向
    labelRegion(image, x+1, y, oldLabel, newLabel);
    labelRegion(image, x-1, y, oldLabel, newLabel);
    labelRegion(image, x, y+1, oldLabel, newLabel);
    labelRegion(image, x, y-1, oldLabel, newLabel);
}

应用特点：

• 可以结合其他算法进行区域特征提取
• 在图像处理中常与边缘检测结合使用
• 可以用于对象识别和场景理解

bool findPath(vector<vector<char>>& maze, 
             pair<int, int> start, 
             pair<int, int> end,
             vector<vector<bool>>& visited,
             vector<pair<int, int>>& path) {
    
    int x = start.first, y = start.second;
    
    // 检查边界和障碍物
    if (x < 0 || x >= maze.size() || 
        y < 0 || y >= maze[0].size() || 
        maze[x][y] == '#' || visited[x][y]) {
        return false;
    }
    
    // 标记当前位置为已访问
    visited[x][y] = true;
    path.push_back({x, y});
    
    // 到达终点
    if (x == end.first && y == end.second) {
        return true;
    }
    
    // 四个方向的移动
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (findPath(maze, {nx, ny}, end, visited, path)) {
            return true;
        }
    }
    
    // 回溯
    path.pop_back();
    return false;
}

区域探索：

• 计算迷宫中可到达的区域
• 统计不同区域的大小
• 找出最大的连通区域
• 检测迷宫中的死胡同和循环

实现示例：

int exploreRegion(vector<vector<char>>& maze, int x, int y) {
    if (x < 0 || x >= maze.size() || 
        y < 0 || y >= maze[0].size() || 
        maze[x][y] == '#') {
        return 0;
    }
    
    // 标记为已访问
    maze[x][y] = '#';
    int size = 1; // 当前格子计入大小
    
    // 探索四个方向
    size += exploreRegion(maze, x+1, y);
    size += exploreRegion(maze, x-1, y);
    size += exploreRegion(maze, x, y+1);
    size += exploreRegion(maze, x, y-1);
    
    return size;
}

int findLargestRegion(vector<vector<char>>& maze) {
    int rows = maze.size();
    int cols = maze[0].size();
    int maxSize = 0;
    
    // 创建迷宫的副本，避免修改原始数据
    vector<vector<char>> mazeCopy = maze;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (mazeCopy[i][j] == '.') { // 空地
                int size = exploreRegion(mazeCopy, i, j);
                maxSize = max(maxSize, size);
            }
        }
    }
    
    return maxSize;
}

应用特点：

• 在游戏开发中广泛应用
• 可用于自动生成迷宫和关卡设计
• 结合A*等算法可以实现更高效的路径寻找
• 可以扩展到三维空间的迷宫问题

代码实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n; // 棋盘大小
vector<vector<int>> board; // 棋盘状态

// 4个方向的移动
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

// 检查一个连通区域是否有"气"
bool hasLiberty(int x, int y, vector<vector<bool>>& visited, 
                vector<pair<int, int>>& stones) {
    int color = board[x][y];
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = true;
    stones.push_back({x, y});
    
    bool hasAir = false;
    
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            // 检查边界
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                continue;
            }
            
            // 如果是空位，则有"气"
            if (board[nx][ny] == 0) {
                hasAir = true;
            }
            // 如果是同色且未访问，则加入队列
            else if (board[nx][ny] == color && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
                stones.push_back({nx, ny});
            }
        }
    }
    
    return hasAir;
}

// 计算被吃掉的棋子数量
int countCaptured(int x, int y, int color) {
    int oppositeColor = (color == 1) ? 2 : 1;
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    int capturedCount = 0;
    
    // 检查四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 检查边界和是否是对方棋子
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && 
            board[nx][ny] == oppositeColor && !visited[nx][ny]) {
            
            vector<pair<int, int>> stones;
            // 如果这个连通区域没有"气"，则被吃掉
            if (!hasLiberty(nx, ny, visited, stones)) {
                capturedCount += stones.size();
                // 移除被吃掉的棋子
                for (auto& [sx, sy] : stones) {
                    board[sx][sy] = 0;
                }
            }
        }
    }
    
    return capturedCount;
}

int main() {
    cin >> n;
    
    // 初始化棋盘
    board.resize(n, vector<int>(n));
    
    // 读入棋盘状态
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    
    // 读入新落子的位置和颜色
    int x, y, color;
    cin >> x >> y >> color;
    
    // 模拟落子
    board[x-1][y-1] = color; // 注意：题目中的坐标从1开始
    
    // 计算被吃掉的棋子数量
    int result = countCaptured(x-1, y-1, color);
    cout << result << endl;
    
    return 0;
}

代码实现：

#include <iostream>
#include <vector>
using namespace std;

int n, m; // 网格的行数和列数
vector<vector<char>> grid; // 存储网格
vector<vector<bool>> visited; // 标记已访问的格子

// 4个方向的移动
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

// 使用DFS进行泛洪填充
int dfs(int x, int y) {
    // 检查边界和是否可访问
    if (x < 0 || x >= n || y < 0 || y >= m || 
        grid[x][y] == '#' || visited[x][y]) {
        return 0;
    }
    
    // 标记为已访问
    visited[x][y] = true;
    int count = 1; // 当前格子计入面积
    
    // 递归处理四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        count += dfs(nx, ny);
    }
    
    return count;
}

int main() {
    cin >> n >> m;
    
    // 初始化网格和访问标记
    grid.resize(n, vector<char>(m));
    visited.resize(n, vector<bool>(m, false));
    
    // 读入网格数据
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    // 读入起点坐标
    int r, c;
    cin >> r >> c;
    
    // 检查起点是否合法
    if (r < 1 || r > n || c < 1 || c > m || 
        grid[r-1][c-1] == '#') {
        cout << "0\n";
        return 0;
    }
    
    // 计算可灌溉的农田面积
    int result = dfs(r-1, c-1); // 注意：题目中的坐标从1开始
    cout << result << endl;
    
    return 0;
}

复杂度分析：

• 时间复杂度：O(N×M)，每个格子最多访问一次
• 空间复杂度：O(N×M)，需要存储网格和访问标记数组

优化建议：

• 可以使用BFS实现，获得更直观的扩散效果
• 可以直接修改原网格作为访问标记
• 可以使用方向数组简化代码
• 对于大规模数据，可以考虑使用迭代而非递归

解题技巧：

1. 处理输入：

// 读入网格大小
while (cin >> w >> h && w && h) {
    // 读入网格数据
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> grid[i][j];
            // 记录起始位置
            if (grid[i][j] == '@') {
                start_x = i;
                start_y = j;
            }
        }
    }
    // 处理当前测试用例
    cout << solve() << endl;
}

2. DFS实现：

int dfs(int x, int y) {
    // 边界检查
    if (x < 0 || x >= h || y < 0 || y >= w) return 0;
    // 检查是否可访问
    if (grid[x][y] == '#' || visited[x][y]) return 0;
    
    visited[x][y] = true;
    int count = 1;
    
    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        count += dfs(nx, ny);
    }
    
    return count;
}

3. 注意事项：

• 每次新的测试用例要重置访问标记
• 可以直接修改原网格作为访问标记
• 使用方向数组简化代码
• 注意处理输入输出格式

4. 代码优化：

• 使用全局变量避免参数传递
• 使用字符数组代替vector节省时间
• 预处理方向数组
• 合理使用引用参数

解题技巧：

1. Counting Rooms实现：

int countRooms(vector<vector<char>>& building) {
    int n = building.size();
    int m = building[0].size();
    int rooms = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (building[i][j] == '.') {
                rooms++; // 发现新房间
                dfs(building, i, j); // 标记整个房间
            }
        }
    }
    
    return rooms;
}

void dfs(vector<vector<char>>& building, int x, int y) {
    if (x < 0 || x >= building.size() || 
        y < 0 || y >= building[0].size() || 
        building[x][y] != '.') {
        return;
    }
    
    building[x][y] = '#'; // 标记为已访问
    
    // 访问四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        dfs(building, nx, ny);
    }
}

2. 灌溉问题实现：

int irrigateField(vector<vector<int>>& field, 
                 vector<Source>& sources) {
    int n = field.size();
    int m = field[0].size();
    vector<vector<bool>> irrigated(n, vector<bool>(m));
    
    // 处理每个灌溉源
    for (const auto& source : sources) {
        bfs(field, irrigated, source);
    }
    
    // 统计灌溉面积
    int area = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (irrigated[i][j]) area++;
        }
    }
    
    return area;
}

3. 优化策略：

• 使用BFS处理多源灌溉
• 使用位运算优化状态标记
• 预处理障碍物信息
• 使用队列优化内存使用

4. 注意事项：

• 处理大规模数据时注意效率
• 考虑多个灌溉源的重叠区域
• 正确处理边界条件
• 注意内存限制

void floodFill(vector<vector<int>>& grid, int x, int y, 
               int oldColor, int newColor, int depth) {
    // 限制递归深度
    if (depth > MAX_DEPTH) return;
    
    // 边界检查
    if (x < 0 || x >= grid.size() || 
        y < 0 || y >= grid[0].size()) {
        return;
    }
    
    // 检查颜色
    if (grid[x][y] != oldColor) {
        return;
    }
    
    grid[x][y] = newColor;
    
    // 递归处理四个方向，增加深度计数
    floodFill(grid, x+1, y, oldColor, newColor, depth+1);
    floodFill(grid, x-1, y, oldColor, newColor, depth+1);
    floodFill(grid, x, y+1, oldColor, newColor, depth+1);
    floodFill(grid, x, y-1, oldColor, newColor, depth+1);
}

void floodFillIterative(vector<vector<int>>& grid, int x, int y, 
                       int oldColor, int newColor) {
    // 边界检查和初始颜色检查
    if (x < 0 || x >= grid.size() || 
        y < 0 || y >= grid[0].size() || 
        grid[x][y] != oldColor) {
        return;
    }
    
    stack<pair<int, int>> s;
    s.push({x, y});
    
    while (!s.empty()) {
        auto [cx, cy] = s.top();
        s.pop();
        
        // 检查是否已处理
        if (grid[cx][cy] != oldColor) {
            continue;
        }
        
        grid[cx][cy] = newColor;
        
        // 检查四个方向
        if (cx+1 < grid.size() && grid[cx+1][cy] == oldColor) {
            s.push({cx+1, cy});
        }
        if (cx-1 >= 0 && grid[cx-1][cy] == oldColor) {
            s.push({cx-1, cy});
        }
        if (cy+1 < grid[0].size() && grid[cx][cy+1] == oldColor) {
            s.push({cx, cy+1});
        }
        if (cy-1 >= 0 && grid[cx][cy-1] == oldColor) {
            s.push({cx, cy-1});
        }
    }
}

队列优化：

• BFS实现中队列可能占用大量内存
• 优化队列使用，减少内存占用
• 使用双端队列或循环队列

内存优化的BFS实现：

void floodFillBFS(vector<vector<int>>& grid, int x, int y, 
                 int oldColor, int newColor) {
    // 边界检查和初始颜色检查
    if (x < 0 || x >= grid.size() || 
        y < 0 || y >= grid[0].size() || 
        grid[x][y] != oldColor) {
        return;
    }
    
    // 使用队列进行BFS
    queue<pair<int, int>> q;
    q.push({x, y});
    grid[x][y] = newColor;  // 立即标记起始点
    
    // 方向数组
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        
        // 检查四个方向
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            // 边界检查和颜色检查
            if (nx >= 0 && nx < grid.size() && 
                ny >= 0 && ny < grid[0].size() && 
                grid[nx][ny] == oldColor) {
                grid[nx][ny] = newColor;  // 立即标记
                q.push({nx, ny});
            }
        }
    }
}

内存优化技巧：

• 使用位运算代替布尔数组
• 使用数组代替STL容器
• 重用已分配的内存
• 使用内存池
• 避免不必要的对象复制
• 使用移动语义（C++11及以上）

示例：使用位运算优化：

// 使用整数的位表示访问状态
vector<vector<int>> visited(n, vector<int>(m/32 + 1, 0));

// 设置位
void setBit(int x, int y) {
    visited[x][y/32] |= (1 << (y % 32));
}

// 检查位
bool checkBit(int x, int y) {
    return visited[x][y/32] & (1 << (y % 32));
}

bool isValid(int x, int y, int rows, int cols) {
    return x >= 0 && x < rows && y >= 0 && y < cols;
}

void floodFill(vector<vector<int>>& grid, int x, int y, 
               int oldColor, int newColor) {
    int rows = grid.size();
    int cols = grid[0].size();
    
    // 边界检查
    if (!isValid(x, y, rows, cols)) {
        return;
    }
    
    // 颜色检查
    if (grid[x][y] != oldColor || grid[x][y] == newColor) {
        return;
    }
    
    grid[x][y] = newColor;
    
    // 方向数组
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    
    // 使用方向数组简化代码
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        floodFill(grid, nx, ny, oldColor, newColor);
    }
}

bool floodFillWithValidation(vector<vector<int>>& grid, 
                            int x, int y, 
                            int oldColor, int newColor) {
    int rows = grid.size();
    int cols = rows > 0 ? grid[0].size() : 0;
    
    // 检查网格是否为空
    if (rows == 0 || cols == 0) {
        return false;
    }
    
    // 检查起始点是否在网格内
    if (x < 0 || x >= rows || y < 0 || y >= cols) {
        return false;
    }
    
    // 检查颜色
    if (oldColor == newColor) {
        return true; // 已经是目标颜色，无需填充
    }
    
    // 执行泛洪填充
    floodFill(grid, x, y, oldColor, newColor);
    return true;
}

异常情况处理：

• 处理空网格
• 处理颜色相同的情况
• 处理大规模数据
• 处理特殊形状的连通区域

处理空网格：

void floodFill(vector<vector<int>>& grid, int x, int y, 
               int oldColor, int newColor) {
    // 检查网格是否为空
    if (grid.empty() || grid[0].empty()) {
        return;
    }
    
    // 其他代码...
}

处理颜色相同的情况：

void floodFill(vector<vector<int>>& grid, int x, int y, 
               int oldColor, int newColor) {
    // 如果新旧颜色相同，直接返回
    if (oldColor == newColor) {
        return;
    }
    
    // 其他代码...
}

处理大规模数据：

void floodFillLarge(vector<vector<int>>& grid, int x, int y, 
                   int oldColor, int newColor) {
    // 使用迭代而非递归
    queue<pair<int, int>> q;
    q.push({x, y});
    grid[x][y] = newColor;
    
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    
    // 分批处理，避免队列过大
    const int BATCH_SIZE = 1000;
    while (!q.empty()) {
        int size = min((int)q.size(), BATCH_SIZE);
        
        for (int i = 0; i < size; i++) {
            auto [cx, cy] = q.front();
            q.pop();
            
            for (int j = 0; j < 4; j++) {
                int nx = cx + dx[j];
                int ny = cy + dy[j];
                
                if (nx >= 0 && nx < grid.size() && 
                    ny >= 0 && ny < grid[0].size() && 
                    grid[nx][ny] == oldColor) {
                    grid[nx][ny] = newColor;
                    q.push({nx, ny});
                }
            }
        }
    }
}

处理特殊形状：

• 长条形区域可能导致栈溢出
• 使用迭代方法处理
• 考虑分块处理
• 使用双向BFS优化

常见应用：

1. 图像处理

   • 区域填充
   • 边界提取
   • 连通区域标记

2. 游戏开发

   • 地图探索
   • 区域控制
   • 迷雾战争

3. 图论问题

   • 连通分量
   • 路径寻找
   • 区域划分

注意事项：

• 边界条件检查
• 内存限制考虑
• 栈溢出预防
• 性能优化权衡

学习建议：

1. 基础巩固

   • 熟练掌握DFS和BFS
   • 理解递归和迭代的区别
   • 练习基本题目

2. 实践应用

   • 实现简单画图工具
   • 编写迷宫游戏
   • 尝试图像处理项目

3. 深入研究

   • 学习相关算法
   • 研究优化技术
   • 探索新应用场景

参考资源：

• 算法书籍
• 在线题库
• 开源项目
• 学术论文