C ++ Сапер бесконечный цикл

Question

C ++ Сапер бесконечный цикл

Я кодирую игру тральщика, и когда пользователь нажимает пустую ячейку, все доступные пустые ячейки также должны быть открыты.
Итак, я использую очередь для этого, но мне кажется, что у меня проблемы с бесконечным циклом, может кто угодно поможет мне.

Заранее спасибо.

Часть кода с проблемой:

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

0

c++infinite-loop minesweeper

Решение

Другие решения

Проблема в том, что ваш цикл обрабатывает ячейки, которые он уже обработал, никогда не останавливаясь.

Я бы обычно вдавался в подробности, но, честно говоря, ваш код трудно соблюдать, поэтому я переписал его для ясности и будущих читателей.

Обратите внимание, что это должно быть правильно, но я не проверял, чтобы подтвердить.

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

2

Источник

Accepted Answer

Такая проблема возникает в нескольких ситуациях. Это фактически вычисление «замыкания» набора экземпляров. Часто встречается при работе с графиками, …

Обычно это решается следующим образом:

Определить 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 медленнее, чем простой поиск индексации в матрице).

1