Description

Xiao H is on a rectangular cordon divided into $n \times m$ cells. Each move, he can move one cell in one of the four directions: up, down, left, or right (he cannot stay still). He cannot leave the cordon; otherwise, he will be killed. He starts with full HP of 6 points, and each step costs 1 point of HP. Once his HP drops to 0, he dies. He can pick up a mouse (what the heck...) along the way to refill his HP to full. As long as he steps onto a cell with a mouse, he can pick it up instantly without spending any time. The mouse on a cell refills instantly, so each time he passes that cell, there is a mouse. Even if he dies upon arriving at a cell with a mouse, he cannot refill his HP by picking it up. Even if he dies at his doorstep, it does not count as having returned home.

There are five types of cells on the map:

0: Obstacle.

1: Empty cell; Xiao H can walk freely.

2: Xiao H’s starting point; also an empty cell.

3: Xiao H’s home.

4: An empty cell with a mouse on it.

Can Xiao H return home safely? If yes, what is the shortest time needed?

Input Format

The first line contains two integers $n, m$, indicating that the map size is $n \times m$.

The next $n$ lines each contain $m$ numbers describing the map.

Output Format

Output one line: if Xiao H cannot return home, output -1; otherwise, output the shortest time he needs to return home.

3 3
2 1 1
1 1 0
1 1 3

4

Hint

For all testdata, $1 \le n, m \le 9$.

2021.9.2 Added a set of hack testdata by @囧仙.

Translated by ChatGPT 5