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