SPOJ Problem MKJUMPS

MAKING JUMPS

Explanation:

This problem requires us to find the minimum no. of cells which can not be visited by the knight among all the paths taken. Or, in other words, we can say, we need to find the maximum no. of cells (or longest path) which this knight can visit starting from cell (0, 0).

So, basically we can find the longest path using DFS (if you are not aware, below are the links provided to learn DFS).

Below is the solution provided. Happy coding!

DFS learning links.
1. http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

Solution:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define in_range(x, y, r, c) (x >= 0 && x < r && y >= 0 && y < c)
#define INF 100000000
#define SIZE 11

using namespace std;
char maze[SIZE][SIZE];
int a[] = {-2, -2, -1, 1, 2, 2, 1, -1}, b[] = {-1, 1, 2, 2, 1, -1, -2, -2}, visitedNodes;

void init(){
    //  Fill the chessboard with #s.
    for(int i=0;i<SIZE;i++)
        for(int j=0;j<SIZE;j++)
            maze[i][j] = '#';
}

void dfs(int x, int y, int r, int c, int cntNodes){
    //  Mark current cell as 'v' which denotes this cell is visited.
    maze[x][y] = 'v';
    bool noRoute = true;
    for(int i=0;i<8;i++){
        //  Find next cell to be visited.
        int tmpX = x + a[i];
        int tmpY = y + b[i];
        //  If the cell lies within the chessboard and is not visited.
        if(in_range(tmpX, tmpY, r, c) && maze[tmpX][tmpY] == '.'){
            noRoute = false;
            //  Run dfs on that cell.
            dfs(tmpX, tmpY, r, c, cntNodes + 1);
        }
    }
    /*  If no more cell can be visited from the current node,
        update maximum path length if current path length
        is greater than the maximum one.*/
    if(noRoute){
        if(visitedNodes < cntNodes)
            visitedNodes = cntNodes;
        //display();
    }
    //  Mark the cell as unvisited, as it might be a part of another path.
    maze[x][y] = '.';
}

int main(){
    int r, x, y, cnt, cas=1;
    while(true){
        scanf("%d", &r);
        if(r == 0)
            break;
        //  Initialize the chessboard.
        init();
        cnt = 0;
        visitedNodes = -INF;
        for(int i=0;i<r;i++){
            scanf("%d%d", &x, &y);
            for(int j=x;j<x + y;j++){
                //  Mark the cells in the chessboard with '.'s which can be visited.
                maze[i][j] = '.';
                //  Update the count of cells which can be visited.
                cnt++;
            }
        }
        //  Run a dfs on cell [0][0], which is the top-left cell.
        dfs(0, 0, SIZE, SIZE, 1);
        int res = cnt - visitedNodes;
        if(res == 1)
            printf("Case %d, 1 square can not be reached.\n", cas++);
        else
            printf("Case %d, %d squares can not be reached.\n", cas++, res);
    }
    return 0;
}

Any suggestions are welcome.