Maze Code to be solved in C++ or Python

Consider the problem of finding a path through a maze from a given start state to a given goal state, where the start position is indicated by the "Pacman" icon and the goal state is a dot. The maze layout will be given to you in a simple text format, where '%' stands for walls, 'P' for the starting position, and '.' for the goal (see sample maze file). For this part of the assignment, all step costs are equal to one.

SelectONEfrom the following search algorithm Group 1 for solving different size mazes

Group 1:

• Depth-first search;
• Breadth-first search;

Run each of the above algorithms on the small maze, medium maze, big maze, and the open maze as seen below. For each problem instance and each search algorithm, report the following:

1. The solution and its path cost;
2. Number of nodes expanded;
3. Maximum tree depth searched;
4. Maximum size of the fringe.

------------------------------------------------------------------------------------------------

small maze :

%%%%%%%%%%%%%%%%%%%%%%

% %% % % %

% %%%%%% % %%%%%% %

%%%%%% P % %

% % %%%%%% %% %%%%%

% %%%% % % %

% %%% %%% % %

%%%%%%%%%% %%%%%% %

%. %% %

%%%%%%%%%%%%%%%%%%%%%%

medium maze:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% P%

% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %

% %% % % %%%%%%% %% %

% %% % % % % %%%% %%%%%%%%% %% %%%%%

% %% % % % % %% %% %

% %% % % % % % %%%% %%% %%%%%% %

% % % % % % %% %%%%%%%% %

% %% % % %%%%%%%% %% %% %%%%%

% %% % %% %%%%%%%%% %% %

% %%%%%% %%%%%%% %% %%%%%% %

%%%%%% % %%%% %% % %

% %%%%%% %%%%% % %% %% %%%%%

% %%%%%% % %%%%% %% %

% %%%%%% %%%%%%%%%%% %% %% %

%%%%%%%%%% %%%%%% %

%. %%%%%%%%%%%%%%%% %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

large maze:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% % % % % % % %

% %%%%%%% % %%% % %%% %%% %%%%%%% % %

% % % % % % % %

%%%%% %%%%% %%% % % % %%% %%%%% % %%%

% % % % % % % % % % % % % %

% %%% % % % %%% %%%%% %%% % %%% %%% %

% % % % % % % % %

%%% %%%%%%%%% %%%%%%% %%% %%% % % % %

% % % % % % %

% % %%%%% % %%% % % %%% % %%% %%% % %

% % % % % % % % % % % % % %

% % % %%%%%%% % %%%%%%%%% %%% % %%% %

% % % % % % % % % %

%%% %%% % %%%%% %%%%% %%% %%% %%%%% %

% % % % % % % % % % % %

% % % % % %%% %%% %%% %%% % % % % % %

% % % % % % % % %

%%% %%%%%%% % % %%%%% %%% % %%% %%%%%

% % % % % % % % % %

%%%%% % % %%%%%%%%% %%%%%%%%%%% % %%%

% % % % % % % % %

% %%% %%%%% %%%%%%%%% %%%%% % % %%% %

% % % % % % %

% % % %%%%% %%% % % % % %%%%%%%%%%%%%

% % % % % % % % % % % %

% % %%% %%% % % % %%%%%%%%% %%% % % %

% % % % % % % % % % % % %

% %%% %%% %%%%% %%% % % %%%%% % %%%%%

% % % % % % % % %

%%% % %%%%% %%%%% %%% %%% % %%% % %%%

% % % % % % % % % % % % % % %

% % %%% % % % % %%%%%%%%% % % % % % %

% % % % % %

% % % % %%% %%% %%%%%%% %%% %%% %%% %

%.% % % % % % % % P%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

open maze:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% P%

% % %

% % %

% % %

% % %

% % %

% % % %

% % % %

% % % %

% % % %

% % % %

% % % %

% % % %

%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%

% % %

% % %

% % %

% %

% %

% %

%. %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%