Ricochet Robots

Time limit1sMemory limit256 MB

Summary

Slide up to four robots on a grid with walls and use the fewest moves within the given limit to stop robot 1 on the target cell.

Level: Medium5 of 10
Topics: BFS, Simulation
Solved: No attempts yet

Problem

A team of at most four robots delivers parts on a factory floor. The floor is a rectangular grid of cells, and each robot occupies one cell. The robots are numbered from 1 to 4 and move in the four orthogonal directions (left, right, up, down). Once a robot starts moving it slides in a straight line and stops only when the next cell ahead of it is a wall, lies outside the floor, or holds another robot. The robots never move at the same time: exactly one robot moves per step.

Find the shortest move sequence that leaves robot 1 on the target cell. Reaching the target may require moving other robots out of the way, or parking a robot so that robot 1 bounces off it.

The target cell does not stop a robot. Only walls, the edges of the floor, and other robots do, so robot 1 has to finish a move on the target instead of sliding across it.

Given the floor plan, the starting cell of every robot, and the target cell, compute the smallest total number of moves that brings robot 1 to the target.

Input

The first line contains the number of robots $n$ , the width $w$ and the height $h$ of the floor in cells, and an upper bound $\ell$ on the number of moves to search.

Each of the next $h$ lines holds one row of the floor as exactly $w$ characters:

W a cell occupied by a wall
X the single target cell
1, 2, 3, 4 the starting cell of a robot
. an empty cell

Output

Print the smallest number of moves that brings robot 1 to the target cell. If no sequence of at most $\ell$ moves does that, print NO SOLUTION.

Constraints

$1 \le n \le 4$
$1 \le w$ , $1 \le h$ , $\max(w, h) \le 10$
$1 \le \ell \le 10$

Examples8

Example 1
Input
```
2 5 4 10
.2...
...W.
WWW..
.X.1.
```
Expected output
```
6
```

Example 2

Input

1 5 4 10
.....
...W.
WWW..
.X.1.

Expected output

NO SOLUTION

Example 3
Input
```
1 2 1 1
1X
```
Expected output
```
1
```
Example 4
Input
```
1 3 1 10
1X.
```
Expected output
```
NO SOLUTION
```
Example 5
Input
```
1 3 1 10
1XW
```
Expected output
```
1
```
Example 6
Input
```
1 1 4 10
X
.
.
1
```
Expected output
```
1
```

Example 7

Input

2 5 4 5
.2...
...W.
WWW..
.X.1.

Expected output

NO SOLUTION

Example 8

Input

4 4 4 3
1..2
.WW.
.WW.
3.X4

Expected output

NO SOLUTION