The Cowherd and the Weaver Girl

Time limit1sMemory limit256 MB

Summary
On an N by N grid, move 1 cell per minute from (0,0) to (N-1,N-1); bridges with given periods are crossable only at some minutes, never twice in a row, and you may add one bridge of period M.
Level

Medium7 of 10

Topics
BFS, Graph, Simulation, Brute force
Solved
No attempts yet

Problem

The Cowherd and the Weaver Girl live in a region made up of many islands and cliffs. The region can be represented as a grid, and moving to a cell adjacent up, down, left, or right takes 1 minute.

The 7th day of the 7th month is the day the Cowherd and the Weaver Girl can cross the magpie bridge and meet. Because of aging, however, the crows and magpies can no longer build a large magpie bridge as they once did. So these days they build bridges on only some cliffs, and even that is hard, so they repeatedly build and dismantle the magpie bridge at a fixed period of several minutes. A magpie bridge, once built, stays up for 1 minute.

For example, if the magpie bridges have periods of 3 minutes and 4 minutes, the times when they can be crossed are the parts marked in green in the figures below.

T = 3T = 4

Since the magpie bridges are this unstable, the Cowherd decided, for safety, not to cross magpie bridges twice in a row.

To help the Cowherd at least a little, the crows and magpies decided to pick exactly one cliff and build one more magpie bridge with period M minutes. However, they cannot build another magpie bridge on a cliff where a magpie bridge is already scheduled to be built, and they cannot build a magpie bridge where a cliff crosses another cliff horizontally and vertically, as shown below.

In the figures below, blue is ordinary ground the Cowherd can cross, black is a cliff, and white is a position where cliffs cross and a magpie bridge cannot be built.

Find the minimum time in which the Cowherd can reach the Weaver Girl.

Input

The first line gives an integer N (2 ≤ N ≤ 10), the number of rows and columns of the terrain, and an integer M (2 ≤ M ≤ 20), the period of the newly built magpie bridge.

The next N lines give N integers each, representing one row of the array, separated by single spaces. Each cell value is between 0 and 20 inclusive.

Each cell value means the following.

  • 1: ordinary ground that can be moved onto
  • 0: a cliff that cannot be crossed
  • an integer of 2 or more: a magpie bridge with a period equal to the written number

The Cowherd starts at the top-left corner of the terrain, (0, 0), and the Weaver Girl lives at the bottom-right corner, (N-1, N-1). The Cowherd leaves the starting point at time 0 minutes. Both the Cowherd's and the Weaver Girl's locations are ordinary ground.

Only cases in which the Cowherd and the Weaver Girl can definitely meet are given. In the given terrain information, it is always possible to build at least one magpie bridge. At a point where a cliff crosses another cliff horizontally and vertically, no magpie bridge is installed.

Output

Print the minimum time in which the Cowherd can reach the Weaver Girl.

Examples1

  1. Example 1

    Input
    5 5
1 1 1 1 1
0 6 0 0 0
1 1 0 1 1
1 1 0 1 1
1 1 0 1 1
    Expected output
    8