Shortest Path Problem

Problem code: ENCD04

Consider a two dimensional array of numbers comprehended between 0 and 9(as shown below). The Matrix can be traversed following any orthogonal direction (i.e., north, south, east and west). Considering that each cell represents a cost, 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 array of size NxM where 1 <= N, M <= 999. Note that the solution for the given example is 24.


		0	3	1	2	9

		7	3	4	9	9

		1	7	5	5	3

		2	3	4	2	5

Input

The input contains several Test cases. Each test case 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 Matrix, containing the numbers separated by spaces. Terminate the input with (no. of rows)N=0.

Output

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

Example

Input:
4
5
0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
1
6
0 1 2 3 4 5
0

Output:
24
15

Author: rscrbv
Date Added: 19-01-2010
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

Are the test cases correct ?

naughty @ 24 Jan 2010 03:33 PM

Are the test cases correct ? Can you please once again cross check them.

test cases are correct.

rscrbv @ 24 Jan 2010 04:02 PM

test cases are correct.

I am constantly getting run

rahulakaneo @ 24 Jan 2010 08:40 PM

I am constantly getting run time error but I don't think I should. There is something definitely faulty with the testcases.

Hint: use memory optimally.

mangalsingh29 @ 24 Jan 2010 09:10 PM

Hint: use memory optimally. and optimize for time also. not a simple problem

Is it possible for you to

saurabh29789 @ 24 Jan 2010 09:44 PM

Is it possible for you to provide another test case  ?? My code gives correct value for this test case and some others that I tested. I wonder where it fails. Please provide atleast one more test case, if possible!

Thanks

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions