top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Minimum no of counts from the knight to reach the king?

+6 votes
3,798 views

A chessboard was given to us. Where in there was a Knight and King was placed on certain positions.
Our aim is to reach the king from the knight in minimum no of counts.As we know, knight can either
move 2 steps vertical/horizontal and 1 step horizontal/vertical. same goes here as well.

Input

Position of Knight.
Position of King.
posted Oct 29, 2013 by Anuj Yadav

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+2 votes
#include<stdio.h>
#include<conio.h>
int main()
{
    int k1,k2;  //position of king
    int h1,h2;  //position of horse
    int mov;

    printf("Enter the position of king\n\tEnter the row =>");
    scanf("%d",&k1);

    printf("Enter the column => ");
    scanf("%d",&k2);

    printf("Enter the position of horse\n\tEnter the row => ");
    scanf("%d",&h1);

    printf("Enter the column");
    scanf("%d",&h2);

    mov=fun(k1,k2,h1,h2);
    if(mov>9000)
        printf("\n\n\tN0 possible move");
    else
        printf("\n\n\tminimun no of move => %d",mov);

}

int fun(int k1,int k2,int g1,int g2)
{
    int a,b;
    if(g1<1 || g2<1 || g1>8 || g2>8)
        return 10000;

    if(k1==g1 && k2==g2)
        return 0;

    if((k1+1==g1 && (k2+1==g2 || k2-1==g2)) || (k1-1==g1 && (k2-1==g2 || k2+1==g2)))
        return 2;

    if((k1==g1 &&(k2+1==g2 || k2-1==g2)) ||(k2==g2 && (k1+1==g1 || k1-1==g1)))
        return 3;

    else
    {
        if(k1<g1)
        {
            if(k2<g2)
            {
                a=fun(k1,k2,g1-1,g2-2);
                b=fun(k1,k2,g1-2,g2-1);
            }
            else
            {
                a=fun(k1,k2,g1-2,g2+1);
                b=fun(k1,k2,g1-1,g2+2);

                if(k2>g2);
                else
                {
                    if(a>9000 || b>9000)
                    {
                        a=fun(k1,k2,g1-1,g2-2);
                        b=fun(k1,k2,g1-2,g2-1);
                    }
                }
            }
        }
        else
        {
            if(k2<g2)
            {
                a=fun(k1,k2,g1+1,g2-2);
                b=fun(k1,k2,g1+2,g2-1);
            }
            else
            {
                a=fun(k1,k2,g1+2,g2+1);
                b=fun(k1,k2,g1+1,g2+2);

                if(k2>g2);
                else
                {
                    if(a>9000 || b>9000)
                    {
                        a=fun(k1,k2,g1+1,g2-2);
                        b=fun(k1,k2,g1+2,g2-1);
                    }
                }
            }
        }

        return((a>b)?b+1:a+1);
    }

}
answer Oct 29, 2013 by Vikas Upadhyay
Similar Questions
+8 votes

Convert the given string into palindrome with minimum number of appends(at end of the given string). O(n) algorithm will be appreciated ??

Input :=> Malayal
Output :=> Malayalam

+8 votes

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

+2 votes

Input: Two strings of same length (say "ababab" "bababa")
Output: Two strings with minimum unique character used in each one ("bbbbbb" & "aaaaaa" for above example)

You can swap A[i] and B[i] for all i between 1 and N, inclusive. You cannot swap two characters within A, or within B. you can only swap a character in A with the character at the same index in B, and with no other character. You can perform this operation zero or more times.

Modify the strings through the operations in such a way that the number of unique characters in the strings is minimum.

+1 vote

For eg: z is changed to y & not y to z ....the value of alphabets are changed from right to left ( eg.in the word apple ,the value of 'e' is reduced to 'd' until it becomes a palindrome or when the value becomes 'a'.

+3 votes

A list contains a set of numbers, one number presents once and other numbers present even no. of times. Find out the number that occurs once in the list.

...