You are given an n x n binary matrix A i.e. it contains only 0 and 1.Now you are at A[1][1] and you want to go to an ending point A[k][k]. The only valid moves are: one step right or one step down only if the block contains 1. You are not allowed to move on a block which contain 0. Now you have to find the minimum number of moves required to reach A[k][k] from A[1][1]. If it is not possible to reach at A[k][k] then print ‘-1’.
Constraints:
1<= T <=10
1<= n <=100
1<=k<=n
A[i][j] = 0 or 1
First line is ‘T’ the number of test cases.
-
First line of each test case contains ‘n’ the size of the matrix and ‘k’.
-
The next n lines contain the n blocks of each row.
Your output should contain the minimum numbers of moves required. If it is not possible to reach at A[k][k] then print ‘-1’.
You need to just focus on whether you can reach A[k][k] from A[1][1].
