UIU: Learn C by Examples: Part: 5



#include <cstdio>
#include <cstring>
#include <queue>

#define ROW 10  // number of Rows in the plane 
#define COL 10  // number of Columns in the plane 

struct node {
    int xPos;   // position of x-coordinate 
    int yPos;   // position of y-coordinate 
    int val;    // number of moves 

    node() {}

    node(int a, int b, int c) {
        xPos = a;
        yPos = b;
        val = c;
    }
};

using namespace std;

// visited node
bool visit [ROW] [COL];

// movement values
int moves [ROW] [COL];

// Checks to see if a particular coordinate is valid 
// we will not consider any negative coordinates 
// for example, (-1, -1) is invalid coordinate 
bool isValid(int xPos, int yPos) {
    if (xPos < 0) return false;
    if (xPos >= ROW) return false;
    if (yPos < 0) return false;
    if (yPos >= COL) return false;

    return true;
}

int main ()
{
    int sourceX, sourceY;
    int destinationX, destinationY;

    // sample value
    sourceX = 1;
    sourceY = 1;

    destinationX = 9;
    destinationY = 9;
    
    memset(visit, false, sizeof visit);
    memset(moves, -1, sizeof moves);

    queue<node> q;
    q.push(node(sourceX, sourceY, 0));
    visit [sourceX] [sourceY] = true;

    // horses move
    int dr [] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dc [] = {2, 1, -1, -2, -2, -1, 1, 2};

    while(!q.empty()) {
        node pop = q.front();
        q.pop();

        if (pop.xPos == destinationX && pop.yPos == destinationY) {
            printf ("number of moves: %d\n", pop.val);
        }

        moves [pop.xPos] [pop.yPos] = pop.val;

        for ( int i = 0; i < 8; i++ ) {
            int newX = pop.xPos + dr [i];
            int newY = pop.yPos + dc [i];
            int newVal = pop.val + 1;

            // if the new position is not valid or 
            // we have been visited it before then 
            // there is no need to push it again in queue 
            if (isValid(newX, newY) && !visit [newX] [newY]) {
                // this node hasn't been visited yet
                visit [newX] [newY] = true;
                q.push(node(newX, newY, newVal));
            }
        }
    }

    // prints the number of moves needed for each coordinates 
    for ( int i = 0; i < ROW; i++ ) {
        for ( int j = 0; j < COL; j++ ) {
            printf ("%d\t", moves [i] [j]);
        }
        printf ("\n");
    }

    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s