BFS shortest path program 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 &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;vector&gt;

using namespace std;

int dfs(string g[30][30], pair&lt;int, int&gt; p)
{
    vector &lt;pair&lt;pair&lt;int, int&gt;, int&gt; &gt; v;
    int visited[30][30] = {0};
    int x, y, k = 0;
    pair &lt;pair&lt;int, int&gt;, int&gt; mj;
    pair &lt;pair&lt;int, int&gt;, int&gt; z;
    pair &lt;int, int&gt; 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 &lt;int, int&gt; p;
    string s, g[30][30];
    cin &gt;&gt; n;
    cin &gt;&gt; m;
    for(int i = 0; i &lt; n; i++)
    {
        cin &gt;&gt; s;
        for(int j = 0; j &lt; s.size(); j++)
        {
            g[i][j] = s.substr(j, 1);
            if(g[i][j] == "P")
                p = make_pair(i, j);
        }
    }
    cout &lt;&lt; dfs(g, p);
    return 0;
}


Sample input:




6
10
##########
#.P#.....#
##.#.K#..#
#..####..#
#........#
##########



Sample output:


14
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 &lt;iostream&gt;
#include &lt;vector&gt;

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&lt;int, int&gt; p)
{
    vector &lt;pair&lt;pair&lt;int, int&gt;, int&gt; &gt; v;
    bool visited[30][30] = {0};
    int x, y, k = 0;
    pair &lt;pair&lt;int, int&gt;, int&gt; mj;
    pair &lt;pair&lt;int, int&gt;, int&gt; z;
    pair &lt;int, int&gt; 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 &lt;int, int&gt; p;
    char s, maze[30][30];
    cin &gt;&gt; n;
    cin &gt;&gt; m;
    for(int i = 0; i &lt; n; i++)
    {
        for(int j = 0; j &lt; m; j++)
        {
            cin &gt;&gt; s;
            maze[i][j] = s;
            if(maze[i][j] == start)
                p = make_pair(i, j);
        }
    }
    cout &lt;&lt; dfs(maze, p) &lt;&lt; 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&lt;pair&lt;pair&lt;int, int&gt;, int&gt; &gt; &amp;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