Paheli and Bhujo got no chills

5

1 votes
Easy
Problem

Bhujo has challenged Paheli to cross a garden with some deep pits. He has divided the garden into a matrix of dimension N*M and has asked her to travel from point A to point B in such a way that she never falls in a pit and reaches her destination in minimum number of steps. At a time Paheli can either go up,down,left or right

INPUT FORMAT

First line contains N and M separated by space.

Next line contains a matrix of size NxM. Paheli is free to walk anywhere except cell with number 0 which corresponds to pits in the garden.

Next two lines contain (x,y) coordinates of point A and B.

It is guaranteed that point A and B lie in the matrix.

Note: Follow 0 based indexing , i.e first cell of matrix is (0,0) and last cell is (N-1,M-1)

OUTPUT FORMAT

Print the answer or -1 if she cannot reach point B.

Constraints##

1<=N,M<=10^6 and N*M<=10^6

Setter: Shubhangi Mehrotra

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?