C++ Minesweeper無限ループ

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
• ループでは、あなたがこの要素（例えばelement.process()）を行う必要があるものは何でもqueue
• ドゥから最初の要素をポップ以下
  • を行う
  • （あなたのケースで隣人）接続されているすべての要素を取ると、次の操作を行います。
    • 要素がsetにすでにある場合、それはsetにない場合、
    • それを無視し、それを追加setと原則は、彼らがしている場合は、queueに隣人を押すことでqueue

にプッシュqueueにまだ入っていないか、まだ処理されていない（そのため、効率的な検索を行うためにsetが必要です）。

あなたの正確な問題に応じて、いくつかのものを最適化することができます。 setを使用する代わりに、2次元マトリックス、またはbitsetを使用します。これはおそらくメモリ（グリッドサイズによります）によりますが、行列を頻繁にリセットする必要がある場合はパフォーマンスの問題が発生する可能性がありますが、O(log N)の代わりにO(1)ルックアップを使用します。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); 
}