Silver Lilypad Pond

Time limit1sMemory limit128 MB

Summary

On a grid with knight moves, place the fewest new lilypads so the cow can travel from start to goal, then count the shortest such paths.

Level: Hard8 of 10
Topics: Graph, Shortest path, BFS, Dynamic programming
Solved: No attempts yet

Problem

Farmer John has built a beautiful rectangular pond for his cows to admire and exercise in. The pond is divided into a grid of $M$ rows and $N$ columns ( $1 \le M \le 30$ ; $1 \le N \le 30$ ). Some cells hold remarkably sturdy lilypads, some hold rocks, and the rest are open water.

Bessie practices her ballet by jumping from lilypad to lilypad. She currently stands on one lilypad and wants to reach another. Every jump Bessie makes is exactly a chess knight's move: one cell in one direction and two cells in the perpendicular direction (or two cells in one direction and one in the perpendicular direction). She may only land on lilypads, never on open water or rocks.

Sometimes Bessie cannot reach her destination because some intermediate lilypads are missing. Ever thrifty, Farmer John wants to add as few new lilypads as possible so that a sequence of knight jumps can carry Bessie from her starting lilypad to her destination lilypad. A new lilypad may be placed only on an open-water cell, never on a rock.

Help Farmer John determine, in order:

the minimum number of additional lilypads he must place so Bessie can reach her destination;
among all placements that use that minimum number of additional lilypads, the minimum number of jumps Bessie needs; and
the number of distinct paths from start to destination that use both that minimum number of additional lilypads and that minimum number of jumps. Two paths are different when the sequence of cells Bessie lands on differs; this count already accounts for every way the additional lilypads can be placed.

Input

Line 1: two space-separated integers $M$ and $N$ .
Lines $2 \ldots M+1$ $2 \dots M + 1$ : line $i+1$ $i + 1$ describes row $i$ $i$ of the pond as $N$ $N$ space-separated integers, using these codes:
- 0 — open water
- 1 — an existing lilypad
- 2 — a rock
- 3 — the lilypad Bessie starts on
- 4 — the lilypad Bessie wants to reach

There is exactly one 3 and exactly one 4.

Output

Line 1: one integer — the minimum number of additional lilypads required. If Bessie can never reach her destination, print -1 and nothing else.
Line 2: one integer — the minimum number of jumps Bessie must make when placing that minimum number of additional lilypads. Omit this line if line 1 is -1.
Line 3: one integer — the number of paths from start to destination that use the minimum number of additional lilypads and the minimum number of jumps. Omit this line if line 1 is -1.

Hint

In the sample pond, two lilypads must be added; the two possible placements are marked with x below:

0 0 0 1 0 0 0 0     0 0 0 1 0 0 0 0
0 x 0 0 0 2 0 1     0 0 0 0 0 2 0 1
0 0 0 0 x 4 0 0     0 0 x 0 x 4 0 0
3 0 0 0 0 0 1 0     3 0 0 0 0 0 1 0

With those additions Bessie needs at least $6$ jumps, and there are exactly two distinct $6$ -jump paths, labelled A through G below:

0 0 0 C 0 0 0 0     0 0 0 C 0 0 0 0
0 B 0 0 0 2 0 F     0 0 0 0 0 2 0 F
0 0 0 0 D G 0 0     0 0 B 0 D G 0 0
A 0 0 0 0 0 E 0     A 0 0 0 0 0 E 0

Examples3

Example 1

Input

4 8
0 0 0 1 0 0 0 0
0 0 0 0 0 2 0 1
0 0 0 0 0 4 0 0
3 0 0 0 0 0 1 0

Expected output

2
6
2

Example 2
Input
```
3 3
3 0 0
0 0 4
0 0 0
```
Expected output
```
0
1
1
```
Example 3
Input
```
3 3
3 2 0
2 0 0
0 0 4
```
Expected output
```
-1
```