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.

- Hints are not available for this problem

Loading...