Problem:
A Two Floors Dungeon It was the last day of the summer camp you strayed into the labyrinth on the way to Komaba Campus, the University of Tokyo. 
The contest has just begun.
Your teammates  must impatiently wait for you.
So you have to escape from this labyrinth as soon as possible. The labyrinth is represented by a grid map.
Initially, each grid  except for walls  and stairs is either on the first floor or on the second floor.
Some grids have a switch which can move up or down some of the grids (the grids on the first floor move to the second floor, and the grids on the second floor  to the first floor). In each step, you can take one of the following actions:  Move to an adjacent grid (includes stairs) on the same floor you  are now in. Move to another floor (if you  are in the stairs grid). Operate the switch (if you  are in a grid  with a switch). Luckily, you have just found a map of the labyrinth for some unknown reason.
Let's calculate the minimum step to escape from the labyrinth, and go to the place your teammates are waiting!  Input The format of the input is as follows.   W  H M 11 M 12 M 13 ...M 1W M 21 M 22 M 23 ...M 2W ........ M H1 M H2 M H3 ...M HW S MS 111 MS 112 MS 113 ...MS 11W MS 121 MS 122 MS 123 ...MS 12W ........ MS 1H1 MS 1H2 MS 1H3 ...MS 1HW MS 211 MS 212 MS 213 ...MS 21W MS 221 MS 222 MS 223 ...MS 22W ........ MS 2H1 MS 2H2 MS 2H3 ...MS 2HW MS S11 MS S12 MS S13 ...MS S1W MS S21 MS S22 MS S23 ...MS S2W ........ MS SH1 MS SH2 MS SH3 ...MS SHW The first line contains two integers W ( 3 ≤ W ≤ 50 ) and H ( 3 ≤ H ≤ 50 ).  They represent the width and height of the labyrinth, respectively. The following H lines represent the initial state of the labyrinth.
Each of M ij is  one of the following symbols:  '#' representing a wall, '|' representing stairs, '_' representing a grid which is initially on the first floor, '^' representing a grid which is initially on the second floor, a lowercase letter from 'a' to 'j' representing a switch the grid has, and the grid is initially on the first floor, an uppercase letter from 'A' to 'J' representing a switch the grid has, and the grid is initially on the second floor, '%' representing  the grid you  are initially in (which is initially on the first floor) or '&' representing  the exit of the labyrinth (which is initially on the first floor). The next line contains one integer S ( 0 ≤ S ≤ 10 ), and then the following SH lines represent the information of the switches.
Each of MS kij is  one of:  '#' if M ij is a '#', '|' if M ij is a '|', '*' if the grid is moved by  the switch represented by the k -th alphabet letter, or '.' otherwise. Note that the grid which contains a switch may be moved by operating the switch.
In this case, you will move together with the grid. You may assume each of the '%' (start) and '&' (goal)  appears  exacyly once, that the map is surround by walls, and that each alphabet in the map is any of the letters from 'A' (or 'a') to S -th alphabet letter.  Output Print the minimum step to reach the goal in one line.
If there is no solution, print "-1". Sample Input 1 6 6
######
#_|A%#
#B#_|#
#^BBa#
#B&A##
######
2
######
#*|*.#
#.#.|#
#*.**#
#...##
######
######
#*|*.#
#*#.|#
#..**#
#..*##
###### Output for the Sample Input 1 21 Sample Input 2 8 3
########
#%||Aa&#
########
2
########
#*||*..#
########
########
#.||*.*#
######## Output for the Sample Input 2 7 Sample Input 3 3 4
###
#%#
#&#
###
0 Output for the Sample Input 3 1 Sample Input 4 3 5
###
#%#
#^#
#&#
###
0 Output for the Sample Input 4 -1

Solution (Python):
from collections import deque
import sys
def main():
    readline = sys.stdin.readline
    write = sys.stdout.write
    W, H = map(int, readline().split())
    MP = [readline() for i in range(H)]
    A = [[-1]*W for i in range(H)]
    B = [[-1]*W for i in range(H)]
    C = [[0]*W for i in range(H)]
    SW0 = 'ABCDEFGHIJ'
    SW1 = 'abcdefghij'
    for i, mp in enumerate(MP):
        Ai = A[i]; Bi = B[i]
        for j, c in enumerate(mp):
            if c == '
                continue
            if c in '^' or c in SW0:
                Ai[j] = 1
                if c != '^':
                    Bi[j] = SW0.index(c)+1
            elif c in '_%&' or c in SW1:
                Ai[j] = 0
                if c == '%':
                    sx = j; sy = i
                elif c == '&':
                    gx = j; gy = i
                elif c != '_':
                    Bi[j] = SW1.index(c)+1
            elif c == '|':
                Bi[j] = 0
                Ai[j] = 2
    S = int(readline())
    for k in range(S):
        MP = [readline() for i in range(H)]
        for i, mp in enumerate(MP):
            Ci = C[i]
            for j, c in enumerate(mp):
                if c == '*':
                    Ci[j] |= (2 << k)

    dist = [[{} for i in range(W)] for j in range(H)]
    dist[sy][sx][0] = 0
    dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
    bc = [0]*(2 << S)
    for i in range(1, 2 << S):
        bc[i] = bc[i ^ (i & -i)] ^ 1
    que = deque([(0, sx, sy, 0)])
    while que:
        state, x, y, d = que.popleft()
        if B[y][x] == 0:
            if state^1 not in dist[y][x]:
                dist[y][x][state^1] = d+1
                que.append((state^1, x, y, d+1))
        elif B[y][x] != -1:
            n_state = state ^ (1 << B[y][x]) ^ (state & 1)
            n_state ^= bc[n_state & C[y][x]] ^ A[y][x]
            if n_state not in dist[y][x]:
                dist[y][x][n_state] = d+1
                que.append((n_state, x, y, d+1))
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if not 0 <= nx < W or not 0 <= ny < H or A[ny][nx] == -1:
                continue
            if A[ny][nx] == 2:
                if state not in dist[ny][nx]:
                    dist[ny][nx][state] = d+1
                    que.append((state, nx, ny, d+1))
            else:
                np = bc[state & C[ny][nx]] ^ A[ny][nx]
                if state&1 == np and state not in dist[ny][nx]:
                    dist[ny][nx][state] = d+1
                    que.append((state, nx, ny, d+1))
    if dist[gy][gx]:
        write("%d\n" % min(dist[gy][gx].values()))
    else:
        write("-1\n")
main()