Question

C Programming Language (Code With C Programming Language)

Problem Title : Which Pawn?

Jojo is playing chess himself to practice his abilities. The chess that Jojo played was N × N. When Jojo was practicing, Jojo suddenly saw a position on his chessboard that was so interesting that Jojo tried to put the pieces of Rook, Bishop and Knight in that position. Every time he put a piece, Jojo counts how many other pieces on the chessboard can be captured in one step. After all the pieces are tried, Jojo has a new idea in his game, which is Jojo will put one of the three pieces above in a position that can capture the most pieces but at the least cost. The cost to use Rook, Bishop and Knight is worth 3,2,1 respectively. Help Jojo calculate the minimum cost in each position that Jojo wants to try.

Note: The three pieces cannot capture a piece if it is blocked by another piece, except Knight who has the ability to be able to jump on other piece. Each chessboard row and column will be numbered from 1 to N. Here are the rules for moving pieces.
• Knight can move 1 horizontal step followed by 2 vertical steps or 1 vertical step followed by 2 horizontal steps that make up the letter L with an amount of 8 possible directions.
• Bishop can make diagonal moves to the top left, top right, bottom left and bottom right.
• Rook can move horizontally to the left, horizontal to the right, vertically up and vertically down.

Format Input

In the first line there are 2 integers N, M, where N represents the size of the chessboard and M represents the number of pieces that were on the original chessboard. The next M lines are 2 integers Xi and Yi representing the position of the initial chess pieces. X represents rows in chessboards numbered 1 through N from top to bottom and Y
represents columns in chessboards numbered 1 to N from left to right. In the next line there are integers Q representing the number of positions that Jojo will try. The next Q line is Ai and Bi represents the position that Jojo will try with the three pieces above.

Format Output

Output Q line with 1 integer X which represents the smallest cost that can capture as many other pieces as possible.

Constraints

• 1 ≤ N ≤ 200
• 1 ≤ M + Q ≤ 40000
• 1 ≤ Ai, Bi, Xi, Yi ≤ N

Sample Input & Output (standard input & output)

3 5
1 1
1 2
1 3
2 1
2 3
4
2 2
Case #1: 3
3 1
Case #2: 1
3 2
Case #3: 1
3 3
Case #4: 1

Explanation:

Following is a description of the starting position of each piece on the chessboard, where 1 means there is a piece at that position and 0 means empty.

1 1 1
1 0 1
0 0 0

Here is a list of the pieces that can be captured by the three pieces in the first query with position 2,2.
Knight can capture 0 pieces.
Bishop can capture 2 pieces that are in [1,1] and [1,3].
Rook can capture 3 pieces that are in [1,2], [2,1], and [2,3].
Because Rook can capture the most pieces, Jojo will use Rook for a fee of 3.

Here is a list of the pieces that can be captured by the three pieces in the third query with position 3,2.
Knight can capture 2 pieces that are in [1,1] and [1,3].
Bishop can capture 2 piece that is in [2,1] and [2,3].
Rook can capture 1 piece that is in [1,2].
Because Knight and Bishop can capture the most pieces, Jojo will use Knight because it costs less which is 1.

Answer 1

#include<stdio.h>

//Displacement of the knight's moves
int a[] = {-2,-1,1,2,2,1,-1,-2};
int b[] = {1,2,2,1,-1,-2,-2,-1};


int rook(int board[200][200], int x, int y, int n){
    int ans=0;
    int a=x-1,b=y-1;
    while(a>=0 && b>=0 && a<n && b<n)
        if(board[a++][b]==1){
            ans++;
            break;
        }
    a=x-1,b=y-1;
    while(a>=0 && b>=0 && a<n && b<n)
        if(board[a--][b]==1){
            ans++;
            break;
        }
    a=x-1,b=y-1;
    while(a>=0 && b>=0 && a<n && b<n)
        if(board[a][b++]==1){
            ans++;
            break;
        }
    a=x-1,b=y-1;
    while(a>=0 && b>=0 && a<n && b<n)
        if(board[a][b--]==1){
            ans++;
            break;
        }
    return ans;
}

int knight(int board[200][200], int x, int y, int n){
    int ans=0;
    int i;
    int x_move,y_move;
    for(i = 0; i < 8;i++){
        x_move=x+a[i]-1;
        y_move=y+b[i]-1;
        if(x_move>=0 && x_move<n && y_move>=0 && y_move<n)
            if(board[x_move][y_move]==1)
                ans++;
    }
    return ans;
}

int bishop(int board[200][200], int x, int y, int n){
    int ans=0;
    int a=x-1,b=y-1;
    while(a>=0 && b>=0 && a<n && b<n)
        if(board[a--][b--]==1){
            ans++;
            break;
        }
    a=x-1,b=y-1;
    while(a>=0 && b>=0 && a<n && b<n)
        if(board[a--][b++]==1){
            ans++;
            break;
        }
    a=x-1,b=y-1;
    while(a>=0 && b>=0 && a<n && b<n)
        if(board[a++][b++]==1){
            ans++;
            break;
        }
    a=x-1,b=y-1;
    while(a>=0 && b>=0 && a<n && b<n)
        if(board[a++][b--]==1){
            ans++;
            break;
        }
    return ans;
}

int main() {
    int n,m;
    int board[200][200]={0};
    int x,y;
    int q;
    int r_ans,k_ans,b_ans;
    int ans;
    scanf("%d%d",&n,&m);
    while(m-- > 0){
        scanf("%d%d",&x,&y);
        board[--x][--y]=1;
    }
    scanf("%d",&q);
    while(q-- > 0){
        scanf("%d%d",&x,&y);
        r_ans=rook(board,x,y,n);
        k_ans=knight(board,x,y,n);
        b_ans=bishop(board,x,y,n);
        
        //Here I've done some basic manipulation to find the correct answer;
         r_ans=r_ans*10+1;
         k_ans=k_ans*10+3;
         b_ans=b_ans*10+2;
         
        ans=(r_ans > b_ans && r_ans > k_ans)?r_ans:(b_ans > k_ans)?b_ans:k_ans;
        
        //Redoing the manipulation and getting the answer
        ans=ans%10;
        if(ans==3)
            ans=1;
        else if(ans==1)
            ans=3;
        printf("%d\n",ans);
    }
    return 0;
    
}