#include
#include
struct Pos
{
int _row{};
int _col{};
Pos(int row, int col) :_row(row)
, _col(col) {
}
Pos() {
}
};
std::stacks;
bool CheckIsAccess(int* a, int row_size, int col_size, Pos cur)
{
//行坐標不合法
if (cur._row <0 || cur._row >= row_size){
return false;
}
//列坐標不合法
if (cur._col <0 || cur._col>=col_size){
return false;
}
//走過路
if (a[cur._row * col_size + cur._col] >0){
return false;
}
return true;
}
bool check_pos(int* maze, int rows, int cols, Pos entry)
{
s.push(entry);
while (!s.empty()) {
Pos cur = s.top();
Pos next = cur;
//記迷宮的出口僅在下邊緣
if (next._row == rows-1){
return true;
}
//試探上面
next._row–;
if (CheckIsAccess(maze,rows,cols, next)){
maze[cur._row * cols + cur._col] = 2;
s.push(next);
continue;
}
//試探下面
next = cur;
next._row++;
if (CheckIsAccess(maze, rows, cols, next)) {
maze[cur._row * cols + cur._col] = 2;
s.push(next);
continue;
}
//試探左面
next = cur;
next._col–; //列開始減
if (CheckIsAccess(maze, rows, cols, next)) {
maze[cur._row * cols + cur._col] = 2;
s.push(next);
continue;
}
//試探右面
next = cur;
next._col++;
if (CheckIsAccess(maze, rows, cols, next)) {
maze[cur._row * cols + cur._col] = 2;
s.push(next);
continue;
}
//回溯,如果其余三個方向均不跳出，則表示無通路
maze[cur._row * cols + cur._col] = 3;//將走過的點標記為3,也可以不標記
//如果此節點無路，就刪除節點
s.pop();
}
return false;
}
int main()
{
int map[10][10] = { 1,1,1,1,1,1,1,1,1,1,
0,0,1,1,1,1,1,1,1,1,
1,0,1,1,1,1,1,1,1,1,
1,0,0,1,1,1,1,1,1,1,
1,1,0,0,0,0,0,1,1,1,
1,1,0,1,1,1,0,1,1,1,
1,1,0,1,1,1,0,1,1,1,
1,1,0,1,1,1,0,1,1,1,
1,1,0,1,1,1,0,0,1,1,
1,1,1,1,1,1,1,0,1,1
};
bool flag = check_pos((int*)map, 10, 10, Pos(1, 0));
}

總結:利用棧的思想，去遍歷每個坐標，可以走的坐標放入棧中，然后每個取遍歷，直到此坐標不能走位置，若不能走，就把此坐標刪除掉，然后彈出下一個坐標即可

總結

以上是生活随笔為你收集整理的利用栈解决深度搜索问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。