The following code is applying the depth-first search and breadth-first search algorithm to find the shortest path from bottom left to top right in a 10 x 10
grid. I need reviews to improve my implementation and code quality.
Graph.h:
#include <iostream>
#pragma once
using namespace std;
struct point{
int x, y;
bool operator>(point pnt){
return (this->x > pnt.x) && (this->y > pnt.y);
}
};
struct node{
char val;
bool visited;
point prev;
node(char v = 0){
val = v;
visited = false;
prev = {-1, -1};
}
};
class GRAPH{
size_t rows, cols;
char route;
node** nodes = nullptr;
public:
GRAPH(size_t n, size_t m, char **vals = nullptr, char rout = '*'){
rows = n;
cols = m;
route = rout;
if(vals){
nodes = new node*[rows];
for(size_t i = 0; i < rows; i++){
nodes[i] = new node[cols];
for(size_t j = 0; j < cols; j++){
nodes[i][j] = (vals[i][j]);
}
}
for(size_t i = 0; i < rows; i++)
delete vals[i];
delete[]vals;
}
}
void display(){
for(size_t i = 0; i < rows; i++){
for(size_t j = 0; j < cols; j++)
cout << nodes[i][j].val << ' ';
cout << '\n';
}
cout << '\n';
}
bool inside_graph(point pnt){
return pnt.x < rows && pnt.y < cols;
}
bool is_on_route(point pnt){
return this->inside_graph(pnt) && this->at(pnt).val == route;
}
node& at(point pnt){
return nodes[pnt.x][pnt.y];
}
point size(){
return {rows, cols};
}
~GRAPH(){
for(size_t i = 0; i < rows; i++)
delete nodes[i];
delete[]nodes;
}
};
Solve.cpp
#include <iostream>
#include <queue>
#include <fstream>
#include "graph.h"
using namespace std;
int dfs_cnt = 0, bfs_cnt = 0;
GRAPH init_graph();
void DFS(GRAPH&, point, point);
void BFS(GRAPH&, point, point);
void solve(GRAPH&, bool);
void mark(GRAPH&, char);
int main()
{
GRAPH graph_for_DFS = init_graph();
DFS(graph_for_DFS, {graph_for_DFS.size().x - 1, 0}, {0, graph_for_DFS.size().y - 1});
mark(graph_for_DFS, '+');
graph_for_DFS.display();
solve(graph_for_DFS, 0);
GRAPH graph_for_BFS = init_graph();
BFS(graph_for_BFS, {graph_for_BFS.size().x - 1, 0}, {0, graph_for_BFS.size().y - 1});
mark(graph_for_BFS, '+');
graph_for_BFS.display();
solve(graph_for_BFS, 1);
return 0;
}
GRAPH init_graph(){
dfs_cnt = bfs_cnt = 0;
ifstream maze("Maze.txt");
size_t n, m;
maze >> n >> m;
char **grid = new char* [n];
for(size_t i = 0; i < n; i++){
grid[i] = new char[m];
maze >> grid[i];
}
maze.close();
return GRAPH(n, m, grid);
}
void DFS(GRAPH& graph, point src, point dest){
dfs_cnt++;
if(src > dest)
return;
point tmp = {src.x - 1, src.y};
if(graph.is_on_route(tmp) && !graph.at(tmp).visited){
graph.at(tmp).visited = true;
graph.at(tmp).prev = src;
DFS(graph, tmp, dest);
}
tmp = {src.x, src.y + 1};
if(graph.is_on_route(tmp) && !graph.at(tmp).visited){
graph.at(tmp).visited = true;
graph.at(tmp).prev = src;
DFS(graph, tmp, dest);
}
}
void BFS(GRAPH& graph, point src, point dest){
queue<point> q;
q.push(src);
point curr = src;
while(!q.empty() && !(curr > dest)){
curr = q.front();
graph.at(curr).visited = true;
q.pop();
point tmp = {curr.x - 1, curr.y};
bfs_cnt++;
if(graph.is_on_route(tmp) && !graph.at(tmp).visited){
q.push(tmp);
graph.at(tmp).visited = true;
graph.at(tmp).prev = curr;
bfs_cnt++;
}
tmp = {curr.x, curr.y + 1};
if(graph.is_on_route(tmp) && !graph.at(tmp).visited){
q.push(tmp);
graph.at(tmp).visited = true;
graph.at(tmp).prev = curr;
bfs_cnt++;
}
}
}
void mark(GRAPH& graph, char mrk){
for(node *tmp = &graph.at({0, graph.size().y - 1}); tmp != &graph.at({graph.size().x - 1, 0}); tmp = &graph.at(tmp->prev))
tmp->val = mrk;
graph.at({graph.size().x - 1, 0}) = mrk;
}
void solve(GRAPH& graph, bool is_BFS){
ofstream sol(is_BFS ? "BFS_Solved_Maze.txt" : "DFS_Solved_Maze.txt");
size_t n = graph.size().x, m = graph.size().y;
sol << (is_BFS? bfs_cnt : dfs_cnt) << '\n';
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++)
sol << graph.at({i, j}).val << ' ';
sol <<'\n';
}
}
Maze.txt
10 10
########**
########**
#######**#
##******##
##*****###
##*****###
#***######
#*########
**########
**########