Capture the Pawns

Easy
0/40
Average time to solve is 15m
2 upvotes
Asked in companies
CIS - Cyber InfrastructureIntuitFlipkart limited

Problem statement

Ninja is learning how to play chess. He is still a beginner, so his friend gave him a simple puzzle. The given situation of the chessboard has only one white Rook ‘R’, some white bishops ‘B’ and some black pawns ‘P’. The task is to find the number of pawns that can be captured by the Rook. Can you help Ninja to solve this problem?

You are given a list of 8 strings of size 8 characters each to describe the position of the pieces. Find the number of pawns that can be captured by the Rook

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
Each test case contains a list of 8 space-separated strings.
Output Format: 
For each test case, print ‘an integer corresponding to the number of pawns that can be captured by the Rook.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
Board[i][j] = {‘R’ , ‘B’, ‘P’, ‘ * ’ }.

Time limit: 1 sec
Sample Input 1:
******** ******** ***R***P ******** ***P****  ******** ***P**** ********
Sample Output 1:
2
Explanation of sample input 1:

altImage

The white rook will attack the pawns at d5 and h6. Hence, the answer is 2.
Sample Input 2:
***P**** ***B**** P**R***P ******** ***P****  ******** ***P**** ********
Sample Output 2:
3
Hint

Find the position of the rook and iterate left, right, up, and down.

Approaches (1)
Searching pawn (Iteratively)

In this approach, we will first iterate through the board and find the position of the white rook. After that, we will iterate left, right, up, and down and find if there exists a pawn or the path is blocked by the bishop. We will count the number of pawns under attack and return the answer.


 

Algorithm:

  • For i in range 0 to 7:
    • For j in range 0 to 7:
      • If BOARD [i][j] is equal to ‘R’:
        • Set R as i and C as j.
        • Break.
  • Set ‘ANS’ as 0 to count the numbers of pawns under attack.
  • Iterating in the downward direction.
  • For i in range R+1 to 7:
    • If BOARD[i][C] == ‘P’ :
      • Found a Pawn.
      • Set ‘ANS’ as ‘ANS’ + 1.
      • Break.
    • If BOARD[i][C] == ‘B’ :
      • Bishop blocked the path.
      • Break.
  • Iterating in upward direction.
  • For i in range R-1 to 0:
    • If BOARD[i][C] == ‘P’ :
      • Found a Pawn.
      • Set ‘ANS’ as ‘ANS’ + 1.
      • Break.
    • If BOARD[i][C] == ‘B’ :
      • Bishop blocked the path.
      • Break.
  • Iterating in right direction.
  • For i in range C+1 to 7:
    • If BOARD[R][i] == ‘P’ :
      • Found a Pawn.
      • Set ‘ANS’ as ‘ANS’ + 1.
      • Break.
    • If BOARD[R][i] == ‘B’ :
      • Bishop blocked the path.
      • Break.
  • Iterating in left direction.
  • For i in range C-1 to 0:
    • If BOARD[R][i] == ‘P’ :
      • Found a Pawn.
      • Set ‘ANS’ as ‘ANS’ + 1.
      • Break.
    • If BOARD[R][i] == ‘B’ :
      • Bishop blocked the path.
      • Break.

 

  • Return ‘ANS’.
Time Complexity

O(1).

 

In this approach, in the worst case, we will be iterating over all 64 squares to find the position of the Rook and then iterating in all four directions to check for pawns under attack. Hence, it takes constant time. Hence, the overall time complexity is O(1).

Space Complexity

O(1)

 

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Capture the Pawns
Full screen
Console