BFS shortest path program

Question

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 <iostream>
#include <string>
#include <vector>

using namespace std;

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

Sample input:

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

Sample output:

14

Answer 1

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

2. 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.

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

4. 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 <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;
}

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<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;
    }
}

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

Answer 2

A few other suggestions:

You are using the and, or, not aliases to the logical operators &&, ||, !. In the C language, those are not reserved words, but macros defined in the header <iso646.h>. In C++, those are supposed to be globally visible without the need for the include file.

They might seem like a good idea at first, if you're not a big fan of punctuation, but I'll give you a couple reasons why you shouldn't use them:

• People in general are not familiar with those aliases. I bet you a good number of C++ programmers don't even know they exits.

• I've never actually seen them in use in any production code, so that might give you a hint about the overall view of the practice.

• The reason these aliases where introduced, I think, was for programmers that didn't have a keyboard with the punctuation chars. But I don't think such keyboards are still being manufactured today, so that renders them obsolete for that purpose.

---

You should use some typedefs for the pairs. This pair<pair<int, int>, int> is not just very cumbersome and error prone to type, but also conveys little information. What is a pair of pair<in,int> and int? What's that thing supposed to be called?

Also typedef the vector<pair<pair<int, int>, int> > to some name that tells the reader the purpose of the vector.

---

while(v.size() != 0)

Would probably be more idiomatic if using empty() instead:

while(!v.empty())

---

std::pair and friends are declared in the <utility> header. So it might be a good idea to explicitly include it to make dependencies clear. At the moment, you are depending on a "residual" include probably from <vector>.