Number Maze

Consider a number maze represented as a two-dimensional array of numbers comprehended between 0 and 9, as exemplified below. The maze can be traversed following any orthogonal direction (i.e., north, south, east, and west). Considering that each cell represents a cost, then finding the minimum cost to travel the maze from an entry point to an exit point may pose you a reasonable challenge.

Your task is to find the minimum cost value to go from the top-left corner to the bottom-right corner of a given number maze of size N × M, where 1 ≤ N, M ≤ 999. Note that the solution for the given example is 24.

Input Specification

The input contains several mazes. The first line contains a positive integer defining the number of mazes that follow. Each maze is defined by: one line with the number of rows, N; one line with the number of columns, M; and N lines, one per each row of the maze, containing the maze numbers separated by spaces.

Output Specification

For each maze, output one line with the required minimum value.

Sample Input

1. 2
2. 4
3. 5
4. 0 3 1 2 9
5. 7 3 4 9 9
6. 1 7 5 5 3
7. 2 3 4 2 5
8. 1
9. 6
10. 0 1 2 3 4 5

download as text file

Output for Sample Input

1. 24
2. 15

download as text file