“Optimizing” Ascent: Navigating Bear-Dangerous Territory in a Binary Matrix Mountain

Let's imagine a “mountain” with n levels (1, 2, …, n), where the levels (or “mountain slices”) are encoded by m × m binary matrices. In each matrix, the value 1 indicates points belonging to the mountain. Both 1s and 0s form a connected region, considering two elements adjacent if they share a common side. Other two constraints are: (i) the mountain slices are “concentric” in the sense that in the positions of 1s at level i (i = 2, …, n), there are also 1s at level (i – 1); (ii) the levels have no common boundary points. In the last-level matrix, there is a single 1 representing the peak. Since all internal points at each level are considered bear-dangerous, we want to climb to the summit using the following method: (i) we can start from any boundary/edge point of level 1; (ii) from the edge of each level to the edge of the next level, we want to reach in the minimum number of steps, ultimately reaching the summit at the top level; (iii) climbing to the next level or moving along the edge of any level is considered safe (these areas are avoided by bears, as they have a fear of heights). If we follow the strategy outlined above, how many steps do we take in dangerous territory from the base to the summit?

Input Specification

The first line of the input contains t, the number of test cases. For each test case: (i) the first line contains n and m, the number of levels and the size of the square matrices (1 < n < 100, 3 < m < 100); (ii) each of the next n · m lines contains m binary values (0/1), separated by one space, giving the elements of the matrices.

Output Specification

For each test case, print a single line to the standard output, containing the number of steps taken in dangerous territory.

Sample Input

1
3 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Output for Sample Input

2

Explanation

The sample input consists of a single test case (t = 1) corresponding to a 3-level mountain coded by 10 × 10 matrices. Bold 1s represent edge points. Underlined 1s represent the accessed dangerous points. At level 1, the edge points of level 2 are accessed by 1 internal step (step (3,9)–(3,8)), and at level 2, the position of the peak point from level 3 is also accessed by 1 internal step (step (5,5)–(5,6)).