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

Question

I'm coding a minesweeper game, and when the user clicks an empty cell, all the reachable empty cells must be opened as well.

I'm using a queue to do so, but it seems like I'm having a trouble with an infinite loop.

The part of the code with the problem:

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

Why do I get an infinite loop?

Answer 1

This kind of problem appears in multiple situations. It's actually calculating the 'closure' of a set of instances. Often also found when handling graphs, ...

It's typically solved in the following way:

• Define a queue that will store all the elements that need to be processed.
• Define an associative container (set) with a key that identifies the items to process and make sure look up is fast (in your case, the key could be the coordinates of the cell)
• Add the first element to the queue and set
• In a loop, do the following
  • Pop the first element from the queue
  • Do whatever you need to do with this element (e.g. element.process())
  • Take all the connected elements (in your case the neighbors) and do the following:
    • if the element is already in the set, ignore it
    • if it is not in the set, add it to the set and push it on the queue

The principle is that you push neighbors on the queue if they are not yet in the queue or have not yet been processed (that's why we need the set, to do the efficient look up).

Depending on your exact problem, you could optimize some things, e.g. instead of using a set, use a 2-dimensional matrix, or bitset. This will probably take more memory (depending on your grid size), and might give performance problems if you need to reset the matrix often, but will give an O(1) lookup instead of O(log N) look up for the set (even an std::unordered_set is slower than a simple indexing lookup in a matrix).