Join Regular Classroom : Visit ClassroomTech

Searching & Sorting | Jumping Beetle | Codewindow.in

We called it as Jumping Beetle A beetle on a board of size M X M squares. Each square has coordinates, a pair of integers (i,j), where, i is the row number and j is the column number. Associated with each square is the coordinates of the square it jumps to when it lands there. as an example, in the 6 X 6 board below, the beetle jumps to (2,3) from (1,1), and jumps to (5,2) from (6,4). If the starting location is given, the target is to see the position of the beetle after a large NO. of jumps.

Input Format:
1st Line Input has 3 comma separated positive integers M,A,B. M is the length of a side of the board (the board is of size M X M). The NO. of jumps the beetle makes is AB (A multiplied by B) The next M lines consist of M pairs of comma separated positive integers, each pair separated by a semicolon(;). The Mth pair in each line i.e k shows the coordinates of the square it jumps to if and only if it lands on square (k,m). Finally, there is one line with a comma separated pair of no. giving the initial position of the Jumping Beetle.

Output Format:
The output is the coordinates of the beetle’s position after A,B moves.

Constraints:
6<= M <=20
1<=A, B<109

Example 1
Input:

6,2,3
2,3;2,4;2,1;3,5;3,4;4,2
4,2;4,1;3,1;3,6;4,4;1,4
1,2;1,3;4,5;5,5;2,1;1,5
6,2;6,1;2,2;5,6;2,6;2,5
3,2;3,3;6,5;6,6;6,3;6,4
5,3;5,4;5,1;5,2;4,6;1,6
1,2

Output:
6,3

Example 2
Input:
6,12,2
2,3;2,4;2,1;3,5;3,4;4,2
4,2;4,1;3,1;3,6;4,4;1,4
1,2;1,3;4,5;5,5;2,1;1,5
6,2;6,1;2,2;5,6;2,6;2,5
3,2;3,3;6,5;6,6;6,3;6,4
5 ,3;5,4;5,1;5,2;4,6;1,6
4 ,3

Output:
6,1

Solution: In C

#include<stdio.h>
#include<string.h>

struct pair{
    int first;
    int second;
};

int main(){
    int n,a,b;
    char ch;
    scanf("%d%c%d%c%d",&n,&ch,&a,&ch,&b);
    struct pair A [n][n];
    int dp[n][n];
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j==n-1){
                scanf("%d%c%d",&A[i][j].first,&ch,&A[i][j].second);
                continue;
            }
            scanf("%d%c%d%c",&A[i][j].first,&ch,&A[i][j].second,&ch);
        }
    }
    int inx,iny,fx,fy,q;
    q=a*b;
    q++;
    scanf("%d%c%d",&inx,&ch,&iny);
    fx=--inx;fy=--iny;
    while(q--){
        if(dp[fx][fy]!=-1){
            int kx=A[fx][fy].first-1;
            int ky=A[fx][fy].second-1;
            fx=kx;
            fy=ky;
            dp[fx][fy]=q;
        }
        else{
            dp[fx][fy]=dp[fx][fy]-q;
            q=q%dp[fx][fy];
        }
    }
    printf("%d,%d",fx+1,fy+1);
}

Also Checkout

Recent Posts
Categories
Pages