please help me this programming project in c++. i would appreciate you giving an
ID: 664074 • Letter: P
Question
please help me this programming project in c++. i would appreciate you giving an example of a sample output. Maze Routing - Lee Algorithm Find a path from S to T by "wave propagation" 18 17 16 15 14 15 14 16 16 18 17 16 15 14 13 14 13 14 15 1 17 18 15 14 13 1 17 16 15 14 13 12 11 18 17 16 15 14 13 14 13 14 15 18 17 16 15 14 13 12 12 13 14 15 7 16 15 14 13 121 14 13 12 11 1010 11 12 13 18|17|16|15|14|1312|11|10| |101 11 17 16 15 14 13 12 11 109 17 1 15 14 13 12 11 1090 9 1011 7 16 15 14 13 12 11 109910 11 18 17 16 15 14 13 12 11 10 98 7 8 7 8 9 10 18 17 16 15 14 13 12 11 1087 6 567 80 18 17 16 15 14 13 12 11 10987 67 8 9 181 17 15| 15| 14| 13 12 18 17 16 15 14 13 12 18 17 16 15 14 13 12 11 18 | 17| 16| t5| 14: t3| 12| 11 18 17 16 16 14 13 12110 2 3 4 6 67 89 1 16|15|14|13 | 12|111. 16 15 14 13 12 11 10 9 3 45 878 910 16 15 14 13 12 11 10 9 84 5 678 9 10 11 5 14 13 12 11 10876587 81011 12 17 16 15 14 13 12 11 10 4 5 67 89 10 11 16| 157113112| 11|101 91817|6|7|8|9|10| 11 | 12 Backtracing Wave propagation Time & space complexity for an M × N grid: O(MN) (huge) 10 11 -18-10-15 16-17 769-10-11-12-, 14 10 15 4-13 12 1 10-9-8707e0 10 11 12 13 14-13 12-1090705|45|67-80-10-11 16 3 2 ID 18-17 13 12 21 18 65 16 17 16 15 14-13 12-13 14Explanation / Answer
#include <iostream>
#include <vector>
#include <stdlib.h>
#include "cell.h"
#include <fstream>
#include <cstddef>
#include <sstream>
#include <queue>
#include <map>
#include <math.h>
using namespace std;
cell **Maze;
int maxsize;
int max_size;
int startx;
int starty;
int endx;
int endy;
class CompareQue{
public:
bool operator()(cell &c1,cell &c2){
if(c1.f==c2.f){
if (c1.ID>c2.ID)
return true;
}
else if (c1.f>c2.f)
return true;
return false;
}
};
priority_queue < cell , vector<cell> , CompareQue > pq;
void drawMaze(int i,int j){
Maze=new cell*[j];
for (int k=0; k<j; k++){
Maze[k]=new cell[i];
}
}
int j=0;
void fillMaze(string s,int k){
if (j==maxsize)
j=0;
if ((k!=startx || j!=starty) && (k!=endx || j!=endy)) {
cell *c=new cell();
c->x=k; c->y=j;
c->g=0; c->h=0; c->f=0;
c->id='i';
if (s=="/")
c->reachable=true;
else
c->reachable=false;
Maze[k][j]=*c;
}
j++;
}
void updatefh(cell *c){
c->h = 10*(abs(c->x-endx)+abs(c->y-endy));
if (c->parent!=0)
c->g=c->parent->g+10;
c->f=c->g+c->h;
}
void findneighbour(cell *c){
cout << c->x << " new " << c->y << endl;
cell *c1;
int xx=c->x;
int yy=c->y;
if (yy+1 < max_size){
yy++;
c1 = &Maze[xx][yy];
if (c1->reachable==true && c1->inque==false && c1->invect==false){
c1->parent = c;
cout << "c is same here also " << c->x << " " << c->y << endl;
updatefh(c1);
c1->ID = c1->g+4;
pq.push(*c1);
c1->inque=true;
}
yy--;
}
if (xx+1 < maxsize){
xx++;
c1 = &Maze[xx][yy];
if (c1->reachable==true && c1->inque==false && c1->invect==false){
c1->parent = c;
updatefh(c1);
c1->ID = c1->g+3;
pq.push(*c1);
c1->inque=true;
}
xx--;
}
if (xx-1 >= 0){
xx--;
c1 = &Maze[xx][yy];
if (c1->reachable==true && c1->inque==false && c1->invect==false){
c1->parent = c;
updatefh(c1);
c1->ID = c1->g+2;
pq.push(*c1);
c1->inque=true;
}
xx++;
}
if (yy-1 >= 0){
yy--;
c1 = &Maze[xx][yy];
if (c1->reachable==true && c1->inque==false && c1->invect==false){
c1->parent = c;
updatefh(c1);
c1->ID = c1->g+4;
pq.push(*c1);
c1->inque=true;
}
yy++;
}
}
vector<cell*> vect;
bool findpath(){
updatefh(&Maze[startx][starty]);
cell *c=&Maze[startx][starty];
pq.push(*c);
c->inque=true;
cell cel=pq.top();
cell *cll=&cel;
pq.pop();
while (cll->id!='e'){
findneighbour(cll);
vect.push_back(cll);
cll->invect=true;
if (pq.size()!=0){
cel = pq.top();
cll = &cel;
pq.pop();
}
else{
cout << "NO PATH EXIST BETWEEN " << "(" << startx << " , " << starty << ")" << " AND " << "(" << endx << " , " << endy << ")" << endl;
return false;
}
}
cout << "SUCCESSFULLY PATH FOUND BETWEEN " << "(" << startx << " , " << starty << ")" << " AND " << "(" << endx <<" , "<< endy <<")" << endl << endl;
return true;
}
void create_app(){
ifstream infile;
outstream outfile;
infile.open("benchmark1.txt");
outfile.open("maze.txt");
string s,temp;
getline(infile,s);
stringstream line(s);
vector<string> Token;
while (line >> temp){ // Split the a string with spaces and store in a vector Token.
Token.push_back(temp);
}
string res = "";
for (int i = 0; i < Token[1].length; i++){
if (Token[1][i] == 'X'){
outfile << res << " " << res;
break;
}
else{
res = res + Token[1][i];
}
}
Token.clear();
getline(infile,s);
string** l = new string*[atoi(res.c_str())];
for (int i = 0; i < atoi(res.c_str()); i++){
l[i] = new string[atoi(res.c_str())];
}
for (int i = 0; i < atoi(res.c_str()); i++){
for (int j = 0; j < atoi(res.c_str()); j++){
l[i][j] = "/";
}
}
for (int i = 0; i < s.length; i++){
while (s[i] != '(')
continue;
else{
i++;
string x;
while (s[i] != " "){
x = s + s[i];
i++;
}
int xx = atoi(x.c_str());
i += 2;
x = "";
while (s[i] != ')'){
x = x + s[i];
i++;
}
int yy = atoi(x.c_str());
l[xx][yy] = '*';
}
}
getline(infile,s);
int xx,yy;
for (int i = 0; i < s.length; i++){
while (s[i] != '(')
continue;
else{
i++;
string x;
while (s[i] != " "){
x = s + s[i];
i++;
}
xx = atoi(x.c_str());
i += 2;
x = "";
while (s[i] != ')'){
x = x + s[i];
i++;
}
int yy = atoi(x.c_str());
l[xx][yy] = '*';
}
}
outfile << xx << " " << yy << endl;
getline(infile,s);
for (int i = 0; i < s.length; i++){
while (s[i] != '(')
continue;
else{
i++;
string x;
while (s[i] != " "){
x = s + s[i];
i++;
}
xx = atoi(x.c_str());
i += 2;
x = "";
while (s[i] != ')'){
x = x + s[i];
i++;
}
int yy = atoi(x.c_str());
l[xx][yy] = '*';
}
}
outfile << xx << " " << yy << endl;
for (int i = 0; i < atoi(res.c_str()); i++){
for (int j = 0; j < atoi(res.c_str())-1; j++){
outfile << l[i][j] << " ";
}
outfile << l[i][atoi(res.c_str())-1] << endl;
}
}
int main(){
create_app();
ifstream infile;
string s,str,temp;
string str = "maze.txt";
infile.exceptions ( std::ifstream::failbit | std::ifstream::badbit );
try {
infile.open(str.c_str());
getline(infile,s);
vector<string> Token;
stringstream line(s);
while (line >> temp){ // Split the a string with spaces and store in a vector Token.
Token.push_back(temp);
}
maxsize = atoi(Token[0].c_str());
max_size = atoi(Token[1].c_str());
drawMaze(maxsize,max_size);
Token.clear();
getline(infile,s);
stringstream line1(s);
while (line1 >> temp){ // Split the a string with spaces and store in a vector Token.
Token.push_back(temp);
}
startx = atoi(Token[0].c_str());
starty = atoi(Token[1].c_str());
cell *c1=new cell();
c1->f=0; c1->g=0; c1->h=0;
c1->x=startx; c1->y=starty;
c1->ID=0; c1->id='s';
c1->reachable=true;
Maze[startx][starty]=*c1;
Token.clear();
getline(infile,s);
stringstream line2(s);
while (line2 >> temp){ // Split the a string with spaces and store in a vector Token.
Token.push_back(temp);
}
endx = atoi(Token[0].c_str());
endy = atoi(Token[1].c_str());
cell *c2=new cell();
c2->f=0; c2->g=0; c2->h=0;
c2->x=endx; c2->y=endy;
c2->ID=0; c2->id='e';
c2->reachable=true;
Maze[endx][endy]=*c2;
Token.clear();
int i=0;
while (!infile.eof()){
getline(infile,s);
stringstream line6(s);
while (line6 >> temp){ // Split the a string with spaces and store in a vector Token.
fillMaze(temp,i);
}
i++;
}
}
catch (std::ifstream::failure e) {
std::cerr << "The File ---- " << str <<" ---- is not Here ";
}
findpath();
return 0;
}
// improve my code
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.