CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Task
- Please solve the maze problem (i.e., find the shortest path from the start point to the finish point) by using BFS or DFS (Python or C++)
- The maze layout can be modeled as an array, and you can use the data file
MazeData.txtif necessary.
MazeData.txt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% S%
% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %
% %% % % %%%%%%% %% %
% %% % % % % %%%% %%%%%%%%% %% %%%%%
% %% % % % % %% %% %
% %% % % % % % %%%% %%% %%%%%% %
% % % % % % %% %%%%%%%% %
% %% % % %%%%%%%% %% %% %%%%%
% %% % %% %%%%%%%%% %% %
% %%%%%% %%%%%%% %% %%%%%% %
%%%%%% % %%%% %% % %
% %%%%%% %%%%% % %% %% %%%%%
% %%%%%% % %%%%% %% %
% %%%%%% %%%%%%%%%%% %% %% %
%%%%%%%%%% %%%%%% %
%E %%%%%%%%%%%%%%%% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Codes
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream fin("MazeData.txt");
typedef pair<int, int> Coord;
const int NPOS = -1;
#define X first
#define Y second
vector<string> map;
vector<vector<Coord>> pre;
Coord st, ed;
for (string s; getline(fin, s) && !s.empty();)
{
map.push_back(s);
pre.push_back(vector<Coord>(s.size(), {NPOS, NPOS}));
for (int i = map.size() - 1, j = 0; j < map[i].size(); ++j)
{
if (map[i][j] == 'S')
st = {i, j};
if (map[i][j] == 'E')
ed = {i, j};
}
}
for (deque<Coord> q(1, st); !q.empty() && pre[ed.X][ed.Y].X == NPOS; q.pop_front())
for (Coord nex : vector<Coord>{
{q.front().X + 1, q.front().Y},
{q.front().X - 1, q.front().Y},
{q.front().X, q.front().Y + 1},
{q.front().X, q.front().Y - 1},
})
if (0 <= nex.X && nex.X < map.size())
if (0 <= nex.Y && nex.Y < map[nex.X].size())
if (map[nex.X][nex.Y] == ' ' || map[nex.X][nex.Y] == 'E')
if (pre[nex.X][nex.Y].X == NPOS)
{
q.push_back(nex);
pre[nex.X][nex.Y] = q.front();
}
if (pre[ed.X][ed.Y].X == NPOS)
return cout << "No Solution.", 0;
for (ed = pre[ed.X][ed.Y]; pre[ed.X][ed.Y].X != NPOS; ed = pre[ed.X][ed.Y])
map[ed.X][ed.Y] = 'X';
for (const auto &s : map)
cout << s << '\n';
}
Results
g++ maze.cpp -o maze.out
$ ./maze.out
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% XXXXXXXXXS%
% %%%%%%%%%%%%%%%%%%%%%%%X%%%%%%%% %
% %% % % %%%%%%%XXX%% %
% %% % % % % %%%% %%%%%%%%%X%% %%%%%
% %% % % % % XXXXX%%X%% %
% %% % % % % % %%%% X%%%XXXX%%%%%% %
% % % % % % %%X%%%%%%%% %
% %% % % %%%%%%%% %%XXXXXXXX%% %%%%%
% %% % %% %%%%%%%%%X%% %
% %%%%%% %%%%%%% %%X%%%%%% %
%%%%%% % %%%% %%X% %
% %%%%%% %%%%% % %%X%% %%%%%
% %%%%%% % %%%%%X%% %
% %%%%%% %%%%%%%%%%%X%% %% %
%%%%%%%%%%XXXXXXXXXXXXXXXXXX%%%%%% %
%EXXXXXXXXX%%%%%%%%%%%%%%%% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%