为什么在使用队列处理扫雷中的相邻单元格时会出现无限循环？

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

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

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

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

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);
}

Answer 2

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

通常通过以下方式解决：

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

原则是如果邻居还没有在 queue 中或者还没有被处理（这就是为什么我们需要 set，以做有效的查找）。

根据你的具体问题，你可以优化一些东西，例如不要使用 set，而是使用二维矩阵或 bitset。这可能会占用更多内存（取决于您的网格大小），如果您需要经常重置矩阵，可能会出现性能问题，但会提供 O(1) 查找而不是 O(log N) 查找 set（即使是 std::unordered_set 也比矩阵中的简单索引查找慢）。

为什么在使用队列处理扫雷中的相邻单元格时会出现无限循环？

Why do I get an infinite loop when processing neighbouring cells in Minesweeper using a queue?

c++

infinite-loop

minesweeper