Positions - Queen & Knight (Greedy Algorithm)

-

 Positions - Queen & Knight (Greedy Algorithm)

PROBLEM STATEMENT :

Given a position of Queen and Knight. Form 8X8 matrix with all position filled with '0' and replace given Queen position with 'Q' and replace given Knight position with 'K'. Find number of possible moves where Queen can be moved on a chessboard from given position and replace the positions with 'q' and Find number of possible moves where Knight can be moved on a chessboard from given position and replace the positions with 'k' and if both queen and knight meets in same position then that position should be replaced with 'x'.

Input Format:
First line consist of row and column position of Queen
First line consist of row and column position of Knight

Output:
8X8 matrix with all possible moves of Queen and Knight.


Example Input/Output 1: 
Input: () 

2 3
4 8
Output: 
0 q q q 0 0 0 0
q q Q q q q x q
0 q q q 0 k 0 0
q 0 q 0 q 0 0 K
0 0 q 0 0 x 0 0
0 0 q 0 0 0 x 0
0 0 q 0 0 0 0 q
0 0 q 0 0 0 0 0

Example Input/Output 2: 
Input: () 

3 2
4 8
Output: 
0 q 0 q 0 0 0 0 
q q q 0 0 0 k 0
q Q q q q x q q
q q q 0 0 0 0 K
0 q 0 q 0 k 0 0
0 q 0 0 q 0 k 0
0 q 0 0 0 q 0 0
0 q 0 0 0 0 q 0


SOLUTION :  (CPP)

Hint:  We can use Greedy algorithm to simplify the solution.
 
#include <iostream>
#include<string.h> //For memset function
using namespace std;

int main()
{
    char a[8][8];
    memset(a,'0',sizeof(a)); //For setting matrix values to '0'
    int qx,qy,kx,ky,i,j,x;
    cin>>qx>>qy>>kx>>ky;
    qx--;
    qy--;
    kx--;
    ky--;
    a[qx][qy]='Q';
    a[kx][ky]='K';
    int a1[]={1,1,1,0,0,-1,-1,-1};
    int a2[]={1,0,-1,1,-1,1,0,-1};
    for(x=0;x<8;++x)
    {
        i=qx+a1[x];
        j=qy+a2[x];
        while(i>=0&&i<8&&j>=0&&j<8)
        {
            a[i][j]='q';
            i+=a1[x];
            j+=a2[x];
        }
    }
    int b1[]={2,2,-2,-2,1,1,-1,-1};
    int b2[]={1,-1,1,-1,2,-2,2,-2};
    for(x=0;x<8;++x)
    {
        i=kx+b1[x];
        j=ky+b2[x];
        if(i>=0&&i<8&&j>=0&&j<8)
        {
            if(a[i][j]=='Q') continue;
            else if(a[i][j]=='q') a[i][j]='x';
            else a[i][j]='k';
        }
    }
    for(i=0;i<8;++i)
    {
        for(j=0;j<8;++j)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}


Never Stop Learning !!


Comments

Post a Comment

Popular Posts

Infix to Postfix Expression

-
Infix to Postfix Expression Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands. Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands. PROBLEM STATEMENT : Transform the algebraic expression with brackets into postfix form. Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one f=postfix form (no expressions like a*b*c). Input : t [the number of expressions <= 100] expression [length <= 400] [other expressions] Text grouped in [ ] does not appear in the input file. Output : The expressions in postfix form, one per line. Example Input: 3 (a+(b*c)) ((a+b)*(z+x)) ((a+t)*((b+(a+c))^(c+d))) Output: abc*+ ab+zx+* at+bac++cd+^* SOLUTION :  Note : We can solve this problem using STACK. Copy Code #include <bits/stdc++.h> int priority(char c) { if(c=='+'|...
Read more

HSL Colors Combination

-
Image
 HSL Colors Combination PROBLEM STATEMENT  Given string str which consists of only 3 letters representing the color,(H) Hue, (S) Saturation, (L) Lightness, called HSL colors. The task is to count the occurrence of ordered triplet “H, S, L” in a given string and give this count as the output. Boundary Condition: 1 <= len(str) <= 1000 Example Input/Output 1: Input: ( ) HHSL Output: 2 Explanation:  There are two triplets of RGB in the given string: => H at index 0, S at index 2, and L at index 3 form one triplet of HSL. => H at index 1, S at index 2, and L at index 3 forms the second triplet of HSL. Example Input/Output 2: Input: ( ) SHL Output: 0 Explanation:  No triplets exist.                                          1)     L EARN THRICE                      ...
Read more

Trailing zeroes in factorial

-
Trailing zeroes in factorial  PROBLEM STATEMENT : Given T testcases and For each testcase an integer N is given as the input. For each input, Find the number of trailing zeroes in N!.    Expected Time Complexity: O(logN) (for Finding Number of trailing Zeroes for each testcase) Expected Auxiliary Space: O(1) Example 1: Input: ( ) 5 Output: 1 Explanation: 5! = 120 so the number of trailing zero is 1. Example 2: Input: ( ) 4 Output: 0 Explanation: 4! = 24 so the number of trailing zero is 0. HINT :     Trailing 0s in n! = Count of 5s in prime factors of n!                 = floor(n/5) + floor(n/25) + floor(n/125) + .. SOLUTION :  Copy Code #include <iostream> using namespace std; int main() { int t; cin>>t; while(t--) { int n,noOfZeroes=0; cin>>n; Trailing 0s in n! = Count of 5s in prime factors of n! while(n>0) { noOfZeroes+=(n/5); n/=5; } ...
Read more