patterncppMinor

BFS shortest path program

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

pathbfsprogramshortest

Problem

The task was to find the shortest path between P and K in a maze. You can move horizontally and vertically, where # is a wall and . is free space. I've had a lot of trouble passing on the int k, which is the path length. I had to make a pair which contains a pair of x and y coordinates and int k.

Could I have done this any better without too much change in the code, especially with the pairs and the while loop? And how good is my code overall?

```
#include
#include
#include

using namespace std;

int dfs(string g[30][30], pair p)
{
vector , int> > v;
int visited[30][30] = {0};
int x, y, k = 0;
pair , int> mj;
pair , int> z;
pair l;
z = make_pair(make_pair(p.first, p.second), 0);
v.push_back(z);
while(v.size() != 0)
{
mj = v.front();
l = mj.first;
x = l.first;
y = l.second;
k = mj.second;
v.erase(v.begin());
if(g[x][y] == "K")
return k;
if((g[x+1][y] == "." or g[x+1][y] == "K") and not(visited[x+1][y]))
{
v.push_back(make_pair(make_pair(x+1, y), k+1));
visited[x+1][y] = 1;
}
if((g[x][y+1] == "." or g[x][y+1] == "K") and not(visited[x][y+1]))
{
v.push_back(make_pair(make_pair(x, y+1), k+1));
visited[x][y+1] = 1;
}
if((g[x-1][y] == "." or g[x-1][y] == "K") and not(visited[x-1][y]))
{
v.push_back(make_pair(make_pair(x-1, y), k+1));
visited[x-1][y] = 1;
}
if((g[x][y-1] == "." or g[x][y-1] == "K") and not(visited[x][y-1]))
{
v.push_back(make_pair(make_pair(x, y-1), k+1));
visited[x][y-1] = 1;
}
}
}

int main()
{
int n, m;
pair p;
string s, g[30][30];
cin >> n;
cin >> m;
for(int i = 0; i > s;
for(int j = 0; j < s.size(); j++)
{
g[i][j] = s.substr(j, 1);
if(g[i][j] == "P")
p =

Solution

-
Please don't use using namespace std (read this).

-
The variable names are really not helping. Why not call a maze a maze instead of g? What are mj, z, l, k? It's hard to follow the logic with names like these.

-
Instead of working with strings like "K", "." and "P" it would be more efficient to use chars, and to give them meaningful names.

-
Instead of int visited[30][30], bool visited[30][30] would be more natural

Here's an alternative version of your code, with some variables renamed, constants used, using char instead of string, not using namespace std:

#include 
#include 

using std::cin;
using std::cout;
using std::pair;
using std::make_pair;
using std::vector;

const char start = 'P';
const char target = 'K';
const char empty = '.';

int dfs(char maze[30][30], pair p)
{
    vector , int> > v;
    bool visited[30][30] = {0};
    int x, y, k = 0;
    pair , int> mj;
    pair , int> z;
    pair  l;
    z = make_pair(make_pair(p.first, p.second), 0);
    v.push_back(z);
    while(v.size() != 0)
    {
        mj = v.front();
        l = mj.first;
        x = l.first;
        y = l.second;
        k = mj.second;
        v.erase(v.begin());
        if (maze[x][y] == target) {
            return k;
        }
        if((maze[x+1][y] == empty or maze[x+1][y] == target) and not(visited[x+1][y]))
        {
            v.push_back(make_pair(make_pair(x+1, y), k+1));
            visited[x+1][y] = true;
        }
        if((maze[x][y+1] == empty or maze[x][y+1] == target) and not(visited[x][y+1]))
        {
            v.push_back(make_pair(make_pair(x, y+1), k+1));
            visited[x][y+1] = true;
        }
        if((maze[x-1][y] == empty or maze[x-1][y] == target) and not(visited[x-1][y]))
        {
            v.push_back(make_pair(make_pair(x-1, y), k+1));
            visited[x-1][y] = true;
        }
        if((maze[x][y-1] == empty or maze[x][y-1] == target) and not(visited[x][y-1]))
        {
            v.push_back(make_pair(make_pair(x, y-1), k+1));
            visited[x][y-1] = true;
        }
    }
}

int main()
{
    int n, m;
    pair  p;
    char s, maze[30][30];
    cin >> n;
    cin >> m;
    for(int i = 0; i > s;
            maze[i][j] = s;
            if(maze[i][j] == start)
                p = make_pair(i, j);
        }
    }
    cout << dfs(maze, p) << std::endl;
    return 0;
}

Next, notice the duplication in this code:

if((maze[x+1][y] == empty or maze[x+1][y] == target) and not(visited[x+1][y]))
{
    v.push_back(make_pair(make_pair(x+1, y), k+1));
    visited[x+1][y] = true;
}
if((maze[x][y+1] == empty or maze[x][y+1] == target) and not(visited[x][y+1]))
{
    v.push_back(make_pair(make_pair(x, y+1), k+1));
    visited[x][y+1] = true;
}

The treatment for (x+1, y) is the same as for (x, y+1), and (x-1, y) and (x, y-1). Extract the duplicated parts to a helper method:

void check_maze_pos(char maze[30][30], int x, int y, int k, vector, int> > &v, bool visited[30][30])
{
    if ((maze[x][y] == empty or maze[x][y] == target) and !visited[x][y])
    {
        v.push_back(make_pair(make_pair(x, y), k + 1));
        visited[x][y] = true;
    }
}

And then you can replace the 4 duplicated cases with these 4 simpler lines:

check_maze_pos(maze, x+1, y, k, v, visited);
check_maze_pos(maze, x, y+1, k, v, visited);
check_maze_pos(maze, x-1, y, k, v, visited);
check_maze_pos(maze, x, y-1, k, v, visited);

You can still improve further:

Eliminate the duplication of the magic number 30 in many places

Simplify the duplicated type definitions using typedef

Code Snippets

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::pair;
using std::make_pair;
using std::vector;

const char start = 'P';
const char target = 'K';
const char empty = '.';

int dfs(char maze[30][30], pair<int, int> p)
{
    vector <pair<pair<int, int>, int> > v;
    bool visited[30][30] = {0};
    int x, y, k = 0;
    pair <pair<int, int>, int> mj;
    pair <pair<int, int>, int> z;
    pair <int, int> l;
    z = make_pair(make_pair(p.first, p.second), 0);
    v.push_back(z);
    while(v.size() != 0)
    {
        mj = v.front();
        l = mj.first;
        x = l.first;
        y = l.second;
        k = mj.second;
        v.erase(v.begin());
        if (maze[x][y] == target) {
            return k;
        }
        if((maze[x+1][y] == empty or maze[x+1][y] == target) and not(visited[x+1][y]))
        {
            v.push_back(make_pair(make_pair(x+1, y), k+1));
            visited[x+1][y] = true;
        }
        if((maze[x][y+1] == empty or maze[x][y+1] == target) and not(visited[x][y+1]))
        {
            v.push_back(make_pair(make_pair(x, y+1), k+1));
            visited[x][y+1] = true;
        }
        if((maze[x-1][y] == empty or maze[x-1][y] == target) and not(visited[x-1][y]))
        {
            v.push_back(make_pair(make_pair(x-1, y), k+1));
            visited[x-1][y] = true;
        }
        if((maze[x][y-1] == empty or maze[x][y-1] == target) and not(visited[x][y-1]))
        {
            v.push_back(make_pair(make_pair(x, y-1), k+1));
            visited[x][y-1] = true;
        }
    }
}

int main()
{
    int n, m;
    pair <int, int> p;
    char s, maze[30][30];
    cin >> n;
    cin >> m;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> s;
            maze[i][j] = s;
            if(maze[i][j] == start)
                p = make_pair(i, j);
        }
    }
    cout << dfs(maze, p) << std::endl;
    return 0;
}

if((maze[x+1][y] == empty or maze[x+1][y] == target) and not(visited[x+1][y]))
{
    v.push_back(make_pair(make_pair(x+1, y), k+1));
    visited[x+1][y] = true;
}
if((maze[x][y+1] == empty or maze[x][y+1] == target) and not(visited[x][y+1]))
{
    v.push_back(make_pair(make_pair(x, y+1), k+1));
    visited[x][y+1] = true;
}

void check_maze_pos(char maze[30][30], int x, int y, int k, vector<pair<pair<int, int>, int> > &v, bool visited[30][30])
{
    if ((maze[x][y] == empty or maze[x][y] == target) and !visited[x][y])
    {
        v.push_back(make_pair(make_pair(x, y), k + 1));
        visited[x][y] = true;
    }
}

check_maze_pos(maze, x+1, y, k, v, visited);
check_maze_pos(maze, x, y+1, k, v, visited);
check_maze_pos(maze, x-1, y, k, v, visited);
check_maze_pos(maze, x, y-1, k, v, visited);

Context

StackExchange Code Review Q#68018, answer score: 4

Revisions (0)

No revisions yet.