AMAZON_HACKON Coding Question – Solved

You are given an 8x8 chess board. The board has your rook denoted by 'R' and the rest of the cells are either blank, denoted by 'B' or they have some piece upon them denoted by 'P'. You can move over the blank cells only. A rook can move along its entire row or column in 1 move, up to the point where blank spaces are available. If current coordinates of a rook are (x, y) then rook can move in the following ways in 1 move: Move from (x, y) to (x-1, y), (x-2, y), (x-3, y) and so on; Move from (x, y) to (x+1, y), (x+2, y), (x+3, y) and so on; Move from (x, y) to (x, y-1), (x, y-2), (x, y-3) and so on; Move from (x, y) to (x, y+1), (x, y+2), (x, y+3) and so on. The rook can't move outside the board. As soon as the rook encounters a 'P' cell in its path it stops and can't move further. The rook needs to reach cell (8,8) in order to prove its worth. Find the minimum number of moves the rook would take to reach cell (8,8) or print -1 if it is impossible to do so. The board follows 1 based indexing. The board contains a single cell with value 'R'. Each string consists of only 3 types of characters: 'P', 'B', or 'R'. Input Format: The first line contains a single integer T, the number of testcases. Lines from 1 to 8 of each test case take input of a string of size 8 denoting the arrangement on the chess board. Output Format: Print the minimum number of moves required to reach cell (8,8) or print -1 if it is impossible to do so. Constraints: 1 <= T <= 10^8, length of each string = 8. Sample Testcase 1: Input: 1 BBBBBBBB BRPPPPPP PBPPPPPP PBPPPPPP PBBBBPPP PPBBBBBB PPPPPPPB PPPPPPPB Output: 5 Explanation: In the first move the rook can move from cell (2,2) to (5,2) as all cells in between are blank, i.e. cells (3,2), (4,2), (5,2) are blank. In the second move the rook can move from cell (5,2) to (5,4) as all cells in between are blank, i.e. cells (5,3), (5,4) are blank. In the third move the rook can move from cell (5,4) to (6,4). In the fourth move the rook can move from cell (6,4) to (6,8). In the fifth move the rook can move from cell (6,8) to (8,8). Path: (2,2) > (5,2) > (5,4) > (6,4) > (6,8) > (8,8). Thus, it took 5 moves for the rook to reach cell (8,8). There might be other possible paths too but none of them would take less than 5 moves. Sample Testcase 2: Input: BBBBBBBB BBBBBBBB RBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBPP BBBBBBPB Output: -1 Explanation: Since cell (8,8) is blocked by pieces ('P') from all directions, it is impossible for the rook to reach cell (8,8) regardless of the path taken.