问题描述:有一张地图,0表示没有障碍物,1表示有障碍物,给你一幅地图、一个起始位置和一个目标位置,请判断是否能够从起始位置出发到达目标位置,可以的话将走过的路径用6进行标记
解题思路:
将起始位置入栈;
拿到栈顶元素,判断栈顶元素是否已经访问过:
如果是让栈顶元素出栈,
如果不是在栈顶元素对应位置的上下左右四个方向进行查找是否有没有被访问过的并且可行的位置,如果有将其入栈;
重复上一步,直到栈为空或者栈顶元素就是目标位置;
如果栈顶元素就是目标位置,返回查找成功;
如果栈为空,说明没有可行的路径,查找失败;
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
struct PosType
{
int _x, _y;
PosType() :_x(0), _y(0)
{
}
PosType(int x, int y) :_x(x), _y(y)
{
}
};
bool operator==(const PosType& pos1, const PosType& pos2)
{
return pos1._x == pos2._x && pos1._y == pos2._y;
}
bool operator!=(const PosType& pos1, const PosType& pos2)
{
return pos1._x != pos2._x || pos1._y != pos2._y;
}
//迷宫输入
void InitMaze(vector<vector<int>>& map)
{
cout << "迷宫地图初始化开始,0表示没有障碍物,1表示有障碍物" << endl;
int row = map.size(), col = map[0].size();
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
cin >> map[i][j];
}
}
cout << "初始化完毕!" << endl;
}
//打印地图
void PrintMap(vector<vector<int>>& map)
{
int row = map.size(), col = map[0].size();
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
cout << map[i][j] << " ";
}
cout << endl;
}
}
//判断是否有从beginPos到endPos的路径,使用栈
bool IsHasPath(vector<vector<int>>& map, PosType beginPos, PosType endPos)
{
int rows = map.size(), cols = map[0].size();
//判断位置是否有效
if (beginPos._x < 0 || beginPos._x >= rows || beginPos._y < 0 || beginPos._y >= cols || endPos._x < 0 || endPos._x >= rows ||
endPos._y < 0 || endPos._y >= cols || map[beginPos._x][beginPos._y] == 1 || map[endPos._x][endPos._y] == 1)
{
return false;
}
stack<PosType> st;
vector<vector<bool>> visited(rows, vector<bool>(cols, false));//判断是否经过
int nextStep[4][2] = { {0,1},{0,-1},{-1,0},{1,0} };
st.push(beginPos);
while (!st.empty() && st.top() != endPos)
{
PosType top = st.top();
if (visited[top._x][top._y])
{
st.pop();
}
visited[top._x][top._y] = true;
map[top._x][top._y] = 6;
for (int i = 0; i < 4; ++i)
{
int curX = top._x + nextStep[i][0];
int curY = top._y + nextStep[i][1];
if (curX < 0 || curX >= rows || curY < 0 || curY >= cols)
{
continue;
}
if (map[curX][curY] == 0 && !visited[curX][curY])
{
st.push(PosType(curX, curY));
}
}
}
if (!st.empty() && st.top() == endPos)
{
map[st.top()._x][st.top()._y] = 6;
return true;
}
else
{
return false;
}
}
void GameStart(vector<vector<int>>& map)
{
int row = map.size(), col = map[0].size();
PosType beginPos, endPos;//起始位置,目标位置
cout << "请输入起始位置下标:" << endl;
cin >> beginPos._x >> beginPos._y;
cout << "请输入目标位置下标:" << endl;
cin >> endPos._x >> endPos._y;
//判断是否可以到达目标位置
bool ret = IsHasPath(map, beginPos, endPos);
if (ret)
{
//可以到达目标位置,打印路径
cout << "可以到达目标位置,路径如下,走过的位置用6表示" << endl;
PrintMap(map);
}
else
{
cout << "无法到达" << endl;
}
}