C++扫雷无限循环
我编码一个扫雷游戏,并且当用户点击的空单元,所有可达空单元必须被打开,以及。 所以,我使用队列来这样做,但似乎我遇到了无限循环的麻烦,可以请任何人帮助我。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();
}
这种问题出现在多种情况下。它实际上是在计算一组实例的'闭包'。通常还发现处理图形时,...
它通常解决了以下方式:
- 定义
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
比在矩阵中进行简单的索引查找)。
非常感谢你 –
的问题是你的循环重新处理的细胞,它已经处理,永不停止。
我通常会细讲,但坦率地说你的代码是难以遵循,所以我已经重写它的清晰度和未来的读者。
请注意,这应该是正确的,但我没有测试确认。
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);
}
非常感谢你 –
问题是什么?请进一步详细说明 – whoan
PS:行和列是单击单元格的索引 –
@whoan感谢您的回复..问题是此循环是无限循环 –