Menu

Maze Problem

发表于 29 Aug 2019 总计 2435字 阅读时间 9分
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.txt if necessary.

MazeData.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                 S%
% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %
% %%   %   %      %%%%%%%   %%     %
% %% % % % % %%%% %%%%%%%%% %% %%%%%
% %% % % % %             %% %%     %
% %% % % % % % %%%%  %%%    %%%%%% %
% %  % % %   %    %% %%%%%%%%      %
% %% % % %%%%%%%% %%        %% %%%%%
% %% %   %%       %%%%%%%%% %%     %
%    %%%%%% %%%%%%%      %% %%%%%% %
%%%%%%      %       %%%% %% %      %
%      %%%%%% %%%%% %    %% %% %%%%%
% %%%%%%      %       %%%%% %%     %
%        %%%%%% %%%%%%%%%%% %%  %% %
%%%%%%%%%%                  %%%%%% %
%E         %%%%%%%%%%%%%%%%        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#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

1

g++ maze.cpp -o maze.out

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

$ ./maze.out
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                        XXXXXXXXXS%
% %%%%%%%%%%%%%%%%%%%%%%%X%%%%%%%% %
% %%   %   %      %%%%%%%XXX%%     %
% %% % % % % %%%% %%%%%%%%%X%% %%%%%
% %% % % % %        XXXXX%%X%%     %
% %% % % % % % %%%% X%%%XXXX%%%%%% %
% %  % % %   %    %%X%%%%%%%%      %
% %% % % %%%%%%%% %%XXXXXXXX%% %%%%%
% %% %   %%       %%%%%%%%%X%%     %
%    %%%%%% %%%%%%%      %%X%%%%%% %
%%%%%%      %       %%%% %%X%      %
%      %%%%%% %%%%% %    %%X%% %%%%%
% %%%%%%      %       %%%%%X%%     %
%        %%%%%% %%%%%%%%%%%X%%  %% %
%%%%%%%%%%XXXXXXXXXXXXXXXXXX%%%%%% %
%EXXXXXXXXX%%%%%%%%%%%%%%%%        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%