my-way-to-the-end

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

SAMPLE INPUT
2
5 5
11100
11111
00011
00001
11111
4 4
1111
1111
1111
0000

SAMPLE OUTPUT
8
-1

Explanation

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].

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: