DMOPC '19 Contest 2 P2 - Squares

View as PDF

Submit solution

Points: 5
Time limit: 3.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are given an N \times M grid of squares. Each square contains a number a_i, 1 \le i \le (N\times M), the cost to travel through that square. You are starting at the most top-left square. At each turn you may choose to move down or right but not both. Find the minimum cost it would take you to travel to the most bottom-right square.

Constraints

In all tests,
2 \le N, M \le 500
1 \le a_i \le 10^6

Input Specification

The first line contains two integers, N and M, the dimensions of the grid of squares (N rows and M columns).
The next N lines each contains M integers, a_i, cost to travel through that square in the grid.

Output Specification

Output on a single line, the minimum sum of costs to travel from the most top-left square to the most bottom-right square.

Sample Input

3 4
3 1 2 4
9 8 7 6
2 8 9 2

Sample Output

18

Explanation for Sample Output

We can take the path 3 \to 1 \to 2 \to 4\to 6 \to 2, which gives us the sum of 18. There are no paths that yield a smaller sum.


Comments


  • 7
    ross_cleary  commented on March 24, 2020, 2:17 p.m.

    Shouldn't the problem type be dynamic programming?