为什么在使用队列处理Minesweeper中的相邻单元时得到无限循环？

Question

我正在编写一个扫雷游戏，当用户单击一个空单元时，所有可访问的空单元也必须打开。

我正在使用一个队列来完成这个任务，但是我似乎遇到了无限循环的麻烦。

代码中存在问题的部分：

queue<int> q;
q.push(row);
q.push(col);

while(!q.empty()){
    int tempRow = q.front();
    int tempCol = q.front();

    if((tempRow-1)>=0 && (tempRow-1)<s && (tempCol-1)>=0 && (tempCol-1)<s && table[tempRow-1][tempCol-1]==' '){q.push(tempRow-1);q.push(tempCol-1);}
    if((tempRow-1)>=0 && (tempRow-1)<s && (tempCol)>=0 && (tempCol)<s && table[tempRow-1][tempCol]==' '){q.push(tempRow-1);q.push(tempCol);}
    if((tempRow-1)>=0 && (tempRow-1)<s && (tempCol+1)>=0 && (tempCol+1)<s && table[tempRow-1][tempCol+1]==' '){q.push(tempRow-1);q.push(tempCol+1);}
    if((tempRow)>=0 && (tempRow)<s && (tempCol-1)>=0 && (tempCol-1)<s && table[tempRow][tempCol-1]==' '){q.push(tempRow);q.push(tempCol-1);}
    if((tempRow)>=0 && (tempRow)<s && (tempCol+1)>=0 && (tempCol+1)<s && table[tempRow][tempCol+1]==' '){q.push(tempRow);q.push(tempCol+1);}
    if((tempRow+1)>=0 && (tempRow+1)<s && (tempCol-1)>=0 && (tempCol-1)<s && table[tempRow+1][tempCol-1]==' '){q.push(tempRow+1);q.push(tempCol-1);}
    if((tempRow+1)>=0 && (tempRow+1)<s && (tempCol)>=0 && (tempCol)<s && table[tempRow+1][tempCol]==' '){q.push(tempRow+1);q.push(tempCol);}
    if((tempRow+1)>=0 && (tempRow+1)<s && (tempCol+1)>=0 && (tempCol+1)<s && table[tempRow+1][tempCol+1]==' '){q.push(tempRow+1);q.push(tempCol+1);}

    view[tempRow][tempCol]=' ';

    q.pop();
    q.pop();
}

为什么我会有一个无限的循环？

Answer 1

这类问题出现在多种情况下。它实际上是计算一组实例的“闭包”。在处理图形时也经常发现，..。

它通常以以下方式解决：

• 定义一个存储需要处理的所有元素的queue。
• 使用一个键定义一个关联容器(set)，该键标识要处理的项，并确保查找速度快(在您的示例中，键可以是单元格的坐标)
• 将第一个元素添加到queue和set
• 在循环中，执行以下
  • 从queue弹出第一个元素
  • 对这个元素做你需要做的任何事情(例如，element.process())
  • 接受所有连接的元素(在您的例子中是邻居)并执行以下操作：
    • 如果元素已经在set中，请忽略它
    • 如果它不在set中，则将其添加到set并将其推到queue上。

​

​

原则是，如果邻居还没有在queue中或者还没有被处理(这就是为什么我们需要set来进行有效的查找)，就可以在queue上推送它们。

根据您的确切问题，您可以优化一些事情，例如，不要使用set，而是使用二维矩阵或bitset。这可能会占用更多的内存(取决于网格大小)，如果需要经常重置矩阵，可能会导致性能问题，但会为O(1)查找而不是O(log N)查找set (甚至std::unordered_set比矩阵中的简单索引查找还要慢)。

Answer 2

问题是您的循环重新处理它已经处理的单元格，永不停止。

我通常会详细介绍，但坦率地说，您的代码很难理解，所以我重新编写了它，以求清晰和未来的读者。

请注意，这应该是正确的，但我还没有测试来确认。

const char empty_cell = ' ';
const char open_cell = 'O'; // This should be something different from empty_cell to help you debug.

const int max_rows = 100; // Replace with your max rows.
const int max_cols = 100; // Replace with your max cols.

// For clarity; means "cell position".
typedef std::pair<int, int> cell_pos;

std::queue<cell_pos> pending;
std::vector<cell_pos> skip; 
// skip should really be an std::unordered_set,
// but I leave it as an exercise for the reader.

// Renamed "row" to "start_row"
// Renamed "col" to "start_col"
pending.push(cell_pos(start_row, start_col));

while (!pending.empty()) {
    auto current = pending.front();
    auto row = current.first;
    auto col = current.second;

    // Requires <algorithm>. This skips the current cell if it's already been processed.
    if (std::find(skip.begin(), skip.end(), current) != skip.end()) {
        continue;
    }

    auto left_row = row - 1;
    auto right_row = row + 1;
    auto top_col = col - 1;
    auto bottom_col = col + 1;

    // Is the left cell empty?
    if (left_row >= 0 && table[left_row][col] == empty_cell) {
        pending.push(cell_pos(left_row, col));
    }
    // Is the right cell empty?
    if (right_row < max_rows && table[right_row][col] == empty_cell) {
        pending.push(cell_pos(right_row, col));
    }
    // Is the top cell empty?
    if (top_col >= 0 && table[row][top_col] == empty_cell) {
        pending.push(cell_pos(row, top_col));
    }
    // is the bottom cell empty?
    if (bottom_col < max_cols && table[row][bottom_col] == empty_cell) {
        pending.push(cell_pos(row, bottom_col));
    }
    // Is the top-left cell empty?
    if (left_row >= 0 && top_col >= 0 && table[left_row][top_col] == empty_cell) {
        pending.push(cell_pos(left_row, top_col));
    }
    // Is the top-right cell empty?
    if (right_row < max_rows && top_col >= 0 && table[right_row][top_col] == empty_cell) {
        pending.push(cell_pos(right_row, top_col));
    }
    // Is the bottom-left cell empty?
    if (left_row >= 0 && bottom_col < max_cols && table[left_row][bottom_col] == empty_cell) {
        pending.push(cell_pos(left_row, bottom_col));
    }
    // Is the bottom-right cell empty?
    if (right_row < max_rows && bottom_col < max_cols && table[right_row][bottom_col] == empty_cell) {
        pending.push(cell_pos(right_row, bottom_col));
    }

    view[row][col] = open_cell;
    pending.pop();
    skip.push_back(current);
}