C++扫雷无限循环

Question

我编码一个扫雷游戏，并且当用户点击的空单元，所有可达空单元必须被打开，以及。 所以，我使用队列来这样做，但似乎我遇到了无限循环的麻烦，可以请任何人帮助我。

谢谢先进。

有问题的部分代码：

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

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


        /*cout<<"Check!";*/ 

        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邻居，如果他们尚未在queue中或尚未处理（这就是为什么我们需要set，以进行高效查找）。

根据你确切的问题，你可以优化一些东西，例如而不是使用set，请使用2维矩阵或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); 
}