Ghost Relocation Puzzle

You are given a rectangular grid map consisting of cells. Each cell is either a wall or a corridor. Walls are denoted by the character # and corridors by .. In addition, some corridors initially contain ghosts, which are represented by lowercase letters (for example, a, b, etc.). You are also given a target configuration in the form of another grid of the same size. In the target grid, a ghost's designated destination is marked with the same letter. It is guaranteed that in both grids, the walls are in the same positions and the set of ghost labels is identical.

Your task is to compute the minimum number of steps needed to move all ghosts from their initial positions to their designated target positions. In each step, you can move any subset (possibly all or none) of the ghosts simultaneously. Each ghost has the following options in one step:

• Stay in the current cell.
• Move to an adjacent cell (up, down, left, or right) if that cell is a corridor (i.e. not a wall).

However, a move is considered valid only if the following conditions are met:

1. No cell ends up with more than one ghost.
2. No pair of ghosts exchange positions in a single step. In other words, if ghost i moves from cell \(x\) to \(y\) and ghost j moves from cell \(y\) to \(x\), such a swap (with \(x \neq y\)) is forbidden.

If it is impossible to reach the target configuration, output -1.

Input Specification (see below) and Output Specification follow.

Note: If there are \(k\) ghosts, then each step considers \(5^k\) possible combined moves (each ghost can choose among 5 moves). Use an appropriate search algorithm (for example, breadth-first search) to determine the minimum number of steps.

inputFormat

The input begins with two integers \(n\) and \(m\) representing the number of rows and columns of the grid (e.g. \(1 \leq n, m \leq 20\)).

This is followed by \(n\) lines, each containing a string of length \(m\), representing the initial grid. In this grid, # denotes a wall, . denotes a corridor, and a lowercase letter denotes a ghost (the underlying cell is a corridor).

After that, there are another \(n\) lines representing the target grid configuration. The target grid has the same format: walls (same positions as the initial grid) and corridors. The designated target cell for each ghost is marked with the ghost's letter.

outputFormat

Output a single integer representing the minimum number of steps needed for all ghosts to reach their target positions, or -1 if it is impossible.

sample

4 4
####
#ab#
#c.#
####
####
#ba#
#.c#
####

2