Rook Movement

A rook is a piece in the strategy board game of chess which can move horizontally or vertically through any number of
unoccupied squares. More formally in one step, the rook can move in any one of the following directions
{ UP , DOWN , LEFT , RIGHT } , any number of squares till the squares are unoccupied.

Given the initial location ( A , B ) of the rook, the final destination ( C , D ) and the orientation of the chess
board, find the minimum number of steps required by the player to move the rook to the desired destination or tell that it is
impossible provided all the other pieces on the chess board are stationary.

Unlike the normal chess board, for this problem the chess board is of the dimensions N x M.
The orientation of the board is represented as 0 / 1 2D string array where 0 denotes empty square and 1
denotes occupied square.

Note: It is guaranteed the initial location and the final destination are empty squares.

Rows are numbered from top to bottom and columns are numbered from left to right.



Input Format

The first four arguments given are the Integers A, B, C and D respectively.
The next argument given is the String array representing the orientation of the chess board of size N x M.

Output Format

Return a single integer denoting the minimum number of steps required to move to the destination and if it is impossible return -1.

Constraints

1 <= N, M <= 1000
1 <= A, C <= N
1 <= B, D <= M

For Example

Input 1:
    A = 1
    B = 1
    C = 4
    D = 5
    E = 00010 
        00011 
        11000 
        01000 
   First Step: (1, 1) -> (1, 3)
   Second Step: (1, 3) -> (4, 3)
   Third Step: (4, 3) -> (4, 5)
    
Output 1:
    3

Input 2:
    A = 1
    B = 1
    C = 4
    D = 1
    E = 00010 
        00011 
        11000 
        01000 
Output 2:
    -1
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Rook Movement on Interview Code Editor
Hints
  • Hints are not available for this problem

Discussion


Loading...
Click here to start solving coding interview questions