Zonal Computing Olympiad 2010, 12 Dec 2009

1:00 pm–4:00 pm IST

Problem 1 : Cheapest Path in a Grid

You are given an N × N grid of numbers. You start at the top left corner of the grid. Your goal is to move to the bottom right corner, constrained by the rules below.

At each step you are allowed to perform one of the following moves, provided you stay within the grid:

  • Move right one step to the next column in the grid.

  • Move down one step to the next row in the grid.

  • One of the columns from 2 to N is special. Let this column be K. If you are currently in row i on column K-1, you can move right to any row j on column K in one step.

The cost of your path is calculated as follows:

  • Add each number that you visit on the grid to your cost.

  • When you make a special move from row i on column K-1 to row j on column K, you incur an additional cost equal to the absolute value of i-j.

Your aim is to compute the minimum cost required to reach the bottom right corner of the grid.

For instance, suppose you have the following grid, where column 3 is the special column.

2 4 -5 4
1 -3 1 -3
-3 2 1 4
9 8 2 1

In this grid, the cheapest path has cost -1. To achieve this, move as follows:

  1. Start at top left corner, cost 2.
  2. Move down one row, add 1, current cost 3.
  3. Move right one column, add -3, current cost 0.
  4. Jump to top row on column 3 (special move), add -5 + 1, current cost -4.
  5. Move down one row, add 1, current cost -3.
  6. Move right one column, add -3, current cost -6.
  7. Move down one row, add 4, current cost -2.
  8. Move down one row to bottom right corner, add 1, final cost -1.

Input format

The first line of the input contains two integers N and K, where N is the number of rows and columns in the grid and K, 2 &le K ≤ N, is the special column. This is followed by N lines of input, each containing N space separated integers. Line i+1 of the input describes the numbers in row i of the grid.

Output format

Your output should be a single line consisting of one integer, the cost of cheapest path from the top left corner to the bottom right corner.

Testdata

In all cases, N ≤ 103.

Sample Input

4 3
2 4 -5 4
1 -3 1 -3
-3 2 1 4
9 8 2 1

Sample Output

-1



Copyright (c) IARCS 2003-2024;   Last Updated: 10 Sep 2010