我已经让我的迷宫解决程序工作了,但它似乎在最终输出的解决方案路径中包括了回溯的空间(它去到而又碰到墙壁不得不掉头的地方)。以下是示例:
![enter image description here](https://istack.dev59.com/jLfG2.webp)
我应该如何防止这种情况发生在下面的当前实现中:
![enter image description here](https://istack.dev59.com/jLfG2.webp)
我应该如何防止这种情况发生在下面的当前实现中:
int dir = 4;
bool visited[Max_Maze][Max_Maze][dir];
for (row = 0; row < size; ++ row)
{
for (col = 0; col < size; ++ col)
{
for (dir = 0; dir < 4; ++ dir)
{
visited[row][col][dir]=false;
}
}
}
bool notSolved = true;
int path = 0;
row = 0;
col = 0;
rowStack.push(row);
colStack.push(col);
while (notSolved)
{
//from perspective of person looking at maze on screen
if (((row-1)>=0)&&(maze[row - 1][col] == 0)&&(visited[row][col][0]==false))
{
// if that space is not out of bounds and if you can go up
// and you have not gone in that direction yet, go up
visited[row][col][0] = true;
row--;
rowStack.push(row);
colStack.push(col);
path++;
}
else if (((col+1)<size)&&(maze[row][col + 1] == 0)&&(visited[row][col][1]==false))
{
//else if you can go right etc., go right
visited[row][col][1] = true;
col++;
rowStack.push(row);
colStack.push(col);
path++;
}
else if (((row+1)<size)&&(maze[row + 1][col] == 0)&&(visited[row][col][2]==false))
{
//else if you can go down etc., go down
visited[row][col][2] = true;
row++;
rowStack.push(row);
colStack.push(col);
path++;
}
else if (((col-1)>=0)&&(maze[row][col - 1] == 0)&&(visited[row][col][3]==false))
{
//else if you can go left etc., go left
visited[row][col][3] = true;
col--;
rowStack.push(row);
colStack.push(col);
path++;
}
else
{
//if stuck
if (path == 0)
{
cout << "No Solution Path" << endl;
notSolved = false;
}
else
{
rowStack.pop();
colStack.pop();
row = rowStack.top();
col = colStack.top();
path--;
}
}
if((maze[row][col] == 0) && (row == (size - 1) && col == (size - 1)))
{
//if we reached an exit
cout << "Solution Path:(in reverse)" << endl;
for (int i = 0; i <= path; i++)
{
cout << "row:" << rowStack.top() << " col:" << colStack.top() << endl;
rowStack.pop();
colStack.pop();
}
notSolved = false;
}
}
需要简单修复还是彻底重构?