Snakes and Ladders - Codechef - Solution

Problem Statement:
Bhuvesh takes out his Snakes and Ladders game and stares at the board, and wonders: If he had absolute control on the die, and could get it to generate any number (in the range 1-6) he desired, what would be the least number of rolls of the die in which he'd be able to reach the destination square (Square Number 100) after having started at the base square (Square Number 1)?

Rules

Bhuvesh has total control over the die and the face which shows up every time he tosses it. You need to help him figure out the minimum number of moves in which he can reach the target square (100) after starting at the base (Square 1).
A die roll which would cause the player to land up at a square greater than 100, goes wasted, and the player remains at his original square. Such as a case when the player is at Square Number 99, rolls the die, and ends up with a 5.
If a person reaches a square which is the base of a ladder, (s)he has to climb up that ladder, and he cannot come down on it. If a person reaches a square which has the mouth of the snake, (s)he has to go down the snake and come out through the tail - there is no way to climb down a ladder or to go up through a snake.

Input

The first line contains the number of tests, T. T testcases follow.

For each testcase, there are 3 lines.

The first line contains the number of ladders and snakes, separated by a comma.
The second is a list of comma separated pairs indicating the starting and ending squares of the ladders. The first point is the square from which a player can ascend and the second point is his final position.
The third is a list of comma separated pairs indicating the starting and ending (mouth and tail) squares of the snakes. the first point is the position of the mouth of the snake and the second one is the tail.
Multiple comma separated pairs of snakes and ladders are separated by a single space.


Output

Output description.

For each of the T test cases, output one integer, each of a new line, which is the least number of moves (or rolls of the die) in which the player can reach the target square (Square Number 100) after starting at the base (Square Number 1). This corresponds to the ideal sequence of faces which show up when the die is rolled.


Constraints

    1 ≤ T ≤ 10
    1 ≤ Number of snakes, Number of ladders ≤ 15


Example

Input:
3
3,7
32,62 42,68 12,98
95,13 97,25 93,37 79,27 75,19 49,47 67,17
5,8
32,62 44,66 22,58 34,60 2,90
85,7 63,31 87,13 75,11 89,33 57,5 71,15 55,25
4,9
8,52 6,80 26,42 2,72
51,19 39,11 37,29 81,3 59,5 79,23 53,7 43,33 77,21

Output:
3
3
5


Solution:

/*
    Assumptions: 
        There always exists a solution - ie.. the graph formed is always connected.
        There is no chain of snakes and ladders.

*/

#include<stdio.h>
#include<vector>
#include<map>
using namespace std;
struct Ladder_Snake
{
    int start,end;
};
class Vertex
{
    public:
    int distance,parent;
    bool isVisited;
    vector<int>adj_list;
    Vertex(){}
    Vertex(int distance,bool isVisited)
    {
        this->distance=distance;
        this->isVisited=isVisited;
    }
};
map<int , Vertex>graph;    // making the graph global
void bfs(int start)
{
    vector<int>q;
    q.push_back(start);
    
    graph[start].isVisited=true;
    graph[start].distance=0;
    graph[start].parent=0;
    
    while(q.size()!=0)
    {
        int v=q[0];
        q.erase(q.begin());
        for(int i=0;i<graph[v].adj_list.size();i++)
        {
            int u=graph[v].adj_list[i];
            if(graph[u].isVisited==false)
            {
                q.push_back(u);
                graph[u].parent=v;
                graph[u].isVisited=true;
                graph[u].distance=graph[v].distance+1;
            }
        }
    }
}

int isStart(int x,struct Ladder_Snake *arr,int n)
{
    for(int i=0;i<n;i++)
        if(arr[i].start==x)
            return arr[i].end;
    return -1;
}
void getNumbers(char*str,int *a,int *b)
{
    int flag=0,start=0,end=0;
    for(int j=0;str[j];j++)
    {
        if(str[j]==',')
            flag=1;continue;
        if(flag==0)
            start=start*10+str[j]-'0';
        else
            end=end*10+str[j]-'0';
    }
    (*a)=start;
    (*b)=end;    
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int ladders,snakes;
        char str[100];
        scanf("%s",str);
        getNumbers(str,&ladders,&snakes);
        
        struct Ladder_Snake ladder[15];
        for(int i=0;i<ladders;i++)
        {
            scanf(" %s",str);
            getNumbers(str,&(ladder[i].start),&(ladder[i].end));
        }
        
        struct Ladder_Snake snake[15];
        for(int i=0;i<snakes;i++)
        {
            scanf("%s",str);
            getNumbers(str,&(snake[i].start),&(snake[i].end));
        }
                
        for(int i=1;i<=100;i++)
        {
            if(isStart(i,snake,snakes)!=-1 || isStart(i,ladder,ladders)!=-1)
                continue;
            graph[i]=Vertex(0,false);
            for(int j=i+1;j<=100 && j<i+7;j++)
            {
                int x,y;
                x=isStart(j,snake,snakes);
                y=isStart(j,ladder,ladders);
                if(x!=-1)
                    graph[i].adj_list.push_back(x);
                else if(y!=-1)
                    graph[i].adj_list.push_back(y);
                else graph[i].adj_list.push_back(j);
            }
        }
        // graph construction completed here.
        // printing the graph.
        bfs(1);
        /*
        for(map<int,Vertex> ::iterator it=graph.begin();it!=graph.end();it++)
        {
            printf("%d -> ",it->first);
            Vertex v=it->second;
            for(int j=0;j<v.adj_list.size();j++)
            {
                printf("%d ",v.adj_list[j]);
            }
            printf("\t\t%d",v.parent);
            printf("\n");
        }
        */
        
        printf("%d\n",graph[100].distance);
        
    }
    return 0;
}