Finding smallest number of moves

Question

We are given a map of sides of length n and m (both n and m are less than 1000), divided into n*m fields (squares of side 1). The map looks (for example) like this:

. z x . x
. x x . .
. . x . x 
x . . n .

Here n=4 and m=5. We start from the field with "z" and we have to get to the field with "n". Suppose we are at position (x, y). Then, we can only move to fields with coordinates: (x+1, y+2), (x+1, y-2), (x-1, y+2), (x-1, y-2), (x+2, y+1), (x+2, y-1), (x-2, y+1), (x-2, y-1).

The next restriction is that we can only move to fields with "." (or "n") - we must avoid fields with "x". We have to compute the smallest number of moves required to get from the field with "z" to the field with "n" (if it's impossible, we have to output "NO"). The correct answer for the given sample map is 3. My program works as follows: we input the map, then we represent it as graph - and then we run the breadth-first search. As far as I've tested, my program outputs correct values.

My biggest concern is that I use too much memory. Also, I wonder if there's a better method for solving such problems.

Here's the code:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m, start, finish;

vector <int> graph[990000];

bool visited[990000];

int mydistance[990000];

queue <int> myqueue;

void BFS(int s){

    mydistance[s]=0;

    myqueue.push(s);

    while (!myqueue.empty()){


        if (visited[finish]){

            return;

        }

        int u=myqueue.front();

        myqueue.pop();

        for (int i=0; i<graph[u].size(); i++){

            if (!visited[graph[u][i]]){

                mydistance[graph[u][i]]=mydistance[u]+1;

                myqueue.push(graph[u][i]);

            }

        }

        visited[u]=true;

    }

}

int main(){

    cin >> n >> m;

    char map[n][m];

    for (int i=0; i<n; i++){

        for (int j=0; j<m; j++){

            char x;

            cin >> x;

            map[i][j]=x;

        }

    }

    for (int i=0; i<n; i++){

        for (int j=0; j<m; j++){

            int a=i*m+j;

            if (map[i][j]=='z'){ start=a; }
            if (map[i][j]=='n'){ finish=a; }

            if ((j<m-1) && (i<n-2)) { if (map[i+2][j+1]!='x'){ graph[a].push_back(a+2*m+1); }} // x+1 y+2
            if ((j<m-1) && (i>1)) { if (map[i-2][j+1]!='x'){ graph[a].push_back(a-2*m+1); }} // x+1 y-2
            if ((j>0) && (i<n-2)) { if (map[i+2][j-1]!='x'){ graph[a].push_back(a+2*m-1); }} // x-1 y+2
            if ((j>0) && (i>1)) { if (map[i-2][j-1]!='x'){ graph[a].push_back(a-2*m-1); }} // x-1 y-2
            if ((j<m-2) && (i<n-1)) { if (map[i+1][j+2]!='x'){ graph[a].push_back(a+m+2); }} // x+2 y+1
            if ((j<m-2) && (i>0)) { if (map[i-1][j+2]!='x'){ graph[a].push_back(a-m+2); }} // x+2 y-1
            if ((j>1) && (i<n-1)) { if (map[i+1][j-2]!='x'){ graph[a].push_back(a+m-2); }} // x-2 y+1
            if ((j>1) && (i>0)) { if (map[i-1][j-2]!='x'){ graph[a].push_back(a-m-2); }} // x-2 y-1

            mydistance[a]=-1;

        }

    }

    BFS(start);

    if (mydistance[finish]==-1) {

        cout <<  "NO";

    } else {

        cout << mydistance[finish];

    }

    return 0;

}

Answer 1

I see a number of things that could help you improve your code.

Use consistent formatting

Almost every other line in the program is a blank line. This doesn't really help readability, and then we have lines like these:

if ((j<m-1) && (i<n-2)) { if (map[i+2][j+1]!='x'){ graph[a].push_back(a+2*m+1); }} // x+1 y+2
if ((j<m-1) && (i>1)) { if (map[i-2][j+1]!='x'){ graph[a].push_back(a-2*m+1); }} // x+1 y-2

First, add some whitespace and second, don't jam nested if statements all on one line like that. These could be reformatted like this:

if ((j < m - 1) && (i < n - 2)) {
    if (map[i + 2][j + 1] != 'x') {
        graph[a].push_back(a + 2 * m + 1);
    }
}                   // x+1 y+2
if ((j < m - 1) && (i > 1)) {
    if (map[i - 2][j + 1] != 'x') {
        graph[a].push_back(a - 2 * m + 1);
    }
}                   // x+1 y-2

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Avoid the use of global variables

graph, visited, mydistance and others are declared as global variables rather than as local variables. It's generally better to explicitly pass variables your function will need rather than using the vague implicit linkage of a global variable. For example, the visited is only used within BFS, so it should be a local variable there instead of a global.

Eliminate "magic numbers"

In a number of cases, the code uses "magic numbers" such as 990000 that have no obvious meaning. These would be better as named constants.

Fix the error

This line may be accepted by your compiler, but it is not compliant with the C++ standard:

char map[n][m];

The reason is that the standard will only allow this if both n and m are const and they are not in this program. One could address that by dynamically allocating the object, as:

char *map = new char[m*n];

And then re-doing all references to change from this:

map[i][j] = x;

To this:

map[i * m + j] = x;

However, I think the better way is in the following suggestion.

Use object orientation

Because you're writing in C++, it would make sense to have methods that operate on a class such as Board and Knight (because the legal moves you describe are those that a knight can make in the game of chess) be member functions rather than separate functions. You may not yet have learned about objects or classes, but they're one of the main strengths of C++ and something you should learn soon if you haven't already. Use objects where they make sense.

Have functions return something useful

Instead of a void function, it would make more sense to have BFS() return the distance.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.