Problem:


Problem G: The Morning after Halloween

You are working for an amusement park as an operator of an obakeyashiki, or a haunted house,
in which guests walk through narrow and dark corridors. The house is proud of their lively
ghosts, which are actually robots remotely controlled by the operator, hiding here and there in
the corridors. One morning, you found that the ghosts are not in the positions where they are
supposed to be. Ah, yesterday was Halloween. Believe or not, paranormal spirits have moved
them around the corridors in the night. You have to move them into their right positions before
guests come. Your manager is eager to know how long it takes to restore the ghosts.

In this problem, you are asked to write a program that, given a floor map of a house, finds the
smallest number of steps to move all ghosts to the positions where they are supposed to be.

A floor consists of a matrix of square cells. A cell is either a wall cell where ghosts cannot move
into or a corridor cell where they can.

At each step, you can move any number of ghosts simultaneously. Every ghost can either stay
in the current cell, or move to one of the corridor cells in its 4-neighborhood (i.e. immediately
left, right, up or down), if the ghosts satisfy the following conditions:

 No more than one ghost occupies one position at the end of the step.

 No pair of ghosts exchange their positions one another in the step.

For example, suppose ghosts are located as shown in the following (partial) map, where a sharp sign ('#) represents a wall cell and 'a', 'b', and 'c' ghosts.

                                                 ####
                                                  ab#
                                                 #c##
                                                 ####

The following four maps show the only possible positions of the ghosts after one step.

                                   ####      ####     ####     ####
                                    ab#      a b#     acb#     ab #
                                   #c##      #c##     # ##     #c##
                                   ####      ####     ####     ####

Input

The input consists of at most 10 datasets, each of which represents a floor map of a house. The format of a dataset is as follows.

w h n
c11c12...c1w
c21c22...c2w
. . ..       .
..           .
          .
..           .
ch1ch2...chw

w, h and n in the first line are integers, separated by a space. w and h are the floor width
and height of the house, respectively. n is the number of ghosts. They satisfy the following constraints.

                            4 ≤ w ≤ 16

      4 ≤ h ≤ 16

      1 ≤ n ≤ 3

Subsequent h lines of w characters are the floor map. Each of cij is either:

    
a '#' representing a wall cell,

   
 a lowercase letter representing a corridor cell which is the initial position of a ghost,

   
 an uppercase letter representing a corridor cell which is the position where the ghost corresponding to its lowercase letter is supposed to be, or

   
 a space representing a corridor cell that is none of the above.

In each map, each of the first n letters from a and the first n letters from A appears once and
only once. Outermost cells of a map are walls; i.e. all characters of the first and last lines are
sharps; and the first and last characters on each line are also sharps. All corridor cells in a
map are connected; i.e. given a corridor cell, you can reach any other corridor cell by following
corridor cells in the 4-neighborhoods. Similarly, all wall cells are connected. Any 2 &times; 2 area on
any map has at least one sharp. You can assume that every map has a sequence of moves of ghosts that restores all ghosts to the positions where they are supposed to be.

The last dataset is followed by a line containing three zeros separated by a space.

Output

For each dataset in the input, one line containing the smallest number of steps to restore ghosts
into the positions where they are supposed to be should be output. An output line should not
contain extra characters such as spaces.

Sample Input

5 5 2
#####
#A#B#
#   #
#b#a#
#####
16 4 3
################
## ########## ##
#    ABCcba    #
################
16 16 3
################
### ##    #   ##
##  #  ##   # c#
#  ## ########b#
# ##  # #   #  #
#  # ##   # # ##
##  a#  # # #  #
### ## #### ## #
##   #   #  #  #
#  ##### # ## ##
####   #B# #   #
##  C#   #   ###
#  # # ####### #
# ######  A##  #
#        #    ##
################
0 0 0

Output for the Sample Input

7
36
77



Sample input:
5 5 2
#####
#A#B#
#   #
#b#a#
#####
16 4 3
################
## ########## ##
#    ABCcba    #
################
16 16 3
################
### ##    #   ##
##  #  ##   # c#
#  ## ########b#
# ##  # #   #  #
#  # ##   # # ##
##  a#  # # #  #
### ## #### ## #
##   #   #  #  #
#  ##### # ## ##
####   #B# #   #
##  C#   #   ###
#  # # ####### #
# ######  A##  #
#        #    ##
################
0 0 0


Sample output:
7
36
77

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    W, H, N = map(int, readline().split())
    if W == H == N == 0:
        return False
    MP = [[0]*W for i in range(H)]

    S = [(i-2, i-2) for i in range(3)]
    T = [(i-2, i-2) for i in range(3)]
    for i in range(H):
        s = readline().strip()
        for j, c in enumerate(s):
            if c == '#':
                MP[i][j] = 1
            elif c != ' ':
                idx = "abcABC".find(c)
                if idx < 3:
                    S[idx] = (j, i)
                else:
                    T[idx-3] = (j, i)

    dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
    que = deque([S[0] + (0,)])
    MM = {S[0]: 0, (-1, -1): -2, (0, 0): -1}
    sx, sy = S[0]
    U = [[0]*W for i in range(H)]
    U[sy][sx] = 1
    G = [[0]]
    cur = 1
    while que:
        x, y, v = que.popleft()
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if MP[ny][nx] or U[ny][nx]:
                continue
            U[ny][nx] = 1
            MM[nx, ny] = cur
            que.append((nx, ny, cur))
            G.append([cur, v])
            G[v].append(cur)
            cur += 1
    MM[-1, -1] = len(G); G.append([len(G)])
    MM[0, 0] = len(G); G.append([len(G)])
    a0 = MM[S[0]]; b0 = MM[S[1]]; c0 = MM[S[2]]
    a1 = MM[T[0]]; b1 = MM[T[1]]; c1 = MM[T[2]]

    L = cur+2
    def check(s):
        que = deque([s])
        D = [-1]*L
        D[s] = 0
        while que:
            v = que.popleft()
            nd = D[v]+1
            for w in G[v]:
                if D[w] != -1:
                    continue
                D[w] = nd
                que.append(w)
        return D

    D1 = check(a1); D2 = check(b1); D3 = check(c1)
    INF = 10**18

    hcost = max(D1[a0], D2[b0], D3[c0])
    D = {(a0, b0, c0): 0}
    que = [(hcost, 0, a0, b0, c0)]
    g_key = (a1, b1, c1)
    push = heappush; pop = heappop
    while que:
        hcost, cost, a, b, c = pop(que)
        key = (a, b, c)
        if key == g_key:
            break
        if D[key] < cost:
            continue
        nd = cost+1
        for na in G[a]:
            d1 = D1[na]
            for nb in G[b]:
                if na == nb or (nb == a and na == b):
                    continue
                d2 = D2[nb]
                for nc in G[c]:
                    if na == nc or nb == nc or (nc == a and na == c) or (nc == b and nb == c):
                        continue
                    n_key = (na, nb, nc)
                    if nd < D.get(n_key, INF):
                        D[n_key] = nd
                        hcost = max(d1, d2, D3[nc]) + nd
                        push(que, (hcost, nd, na, nb, nc))
    write("%d\n" % D[g_key])
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
def solve():
    from heapq import heappush, heappop
    from itertools import product
    from sys import stdin
    file_input = stdin
    
    while True:
        w, h, n = map(int, file_input.readline().split())
        if w == 0:
            break
        
        h -= 2
        w -= 2
        
        m = "" # one dimension map
        m_size = h * w
        file_input.readline()
        for i in range(h):
            m += file_input.readline()[1:w+1]
        file_input.readline()
        
        adj = [[i] for i in range(m_size)]
        start = []
        goal = []
        for i, t in enumerate(zip(m, adj)):
            c, a = t
            if c == '#':
                continue
            row = i // w
            col = i % w
            if row > 0 and m[i - w] != '#':
                a.append(i - w)
            if row < (h - 1) and m[i + w] != '#':
                a.append(i + w)
            if col > 0 and m[i - 1] != '#':
                a.append(i - 1)
            if col < (w - 1) and m[i + 1] != '#':
                a.append(i + 1)
            if c.islower():
                start.append(i)
                goal.append(m.index(c.upper()))
        start = tuple(start)
        goal = tuple(goal)
        
        if n == 1:
            # Bidirectional search using breadth-first search
            start = start[0]
            goal = goal[0]
            memo = [set(), set()] # 0: forward, 1: backward
            memo[0].add(start)
            memo[1].add(goal)
            step = {start: 0, goal: 0}
            s = 0
            state = [(start, 0), (goal, 1)]
            
            while state:
                t_state = state[:]
                state.clear()
                s += 1
                for pos, d in t_state:
                    for next_pos in adj[pos]:
                        if next_pos in memo[d]:
                            continue
                        if next_pos in memo[not d]:
                            print(s + step[next_pos])
                            t_state.clear()
                            state.clear()
                            break
                        state.append((next_pos, d))
                        memo[d].add(next_pos)
                        step[next_pos] = s
            continue
        
        # Calculation of single path cost for A* algorithm
        path_cost = [[0] * m_size for i in range(n)]
        for g, p_c in zip(goal, path_cost):
            for i, p in enumerate(m):
                if p == '#' or i == g:
                    continue
                # Bidirectional search using breadth-first search
                memo = [set(), set()] # 0: forward, 1: backward
                memo[0].add(i)
                memo[1].add(g)
                step = {i: 0, g: 0}
                s = 0
                state = [(i, 0), (g, 1)]
                
                while state:
                    t_state = state[:]
                    state.clear()
                    s += 1
                    for pos, d in t_state:
                        for next_pos in adj[pos]:
                            if next_pos in memo[d]:
                                continue
                            if next_pos in memo[not d]:
                                p_c[i] = s + step[next_pos]
                                t_state.clear()
                                state.clear()
                                break
                            state.append((next_pos, d))
                            memo[d].add(next_pos)
                            step[next_pos] = s
        
        # A* algorithm
        h_cost = max(p_c[s] for s, p_c in zip(start, path_cost))
        
        if n == 2:
            if start == goal:
                print(0)
                continue
            state = (h_cost, start)
            q = [state]
            step = [[0 for j in range(m_size)] for i in range(m_size)]
            step[start[0]][start[1]] = 1
            pc1, pc2 = path_cost
            
            while q:
                h_cost, pos = heappop(q)
                p1, p2 = pos
                if pos == goal:
                    print(step[p1][p2] - 1)
                    break
                
                nps1, nps2 = adj[pos[0]], adj[pos[1]]
                for np1, np2 in product(nps1, nps2):
                    if step[np1][np2] or np1 == np2 or pos == (np2, np1):
                        continue
                    s = step[p1][p2]
                    new_h_cost = s + max(pc1[np1], pc2[np2])
                    new_state = (new_h_cost, (np1, np2))
                    heappush(q, new_state)
                    step[np1][np2] = s + 1
            continue
        
        if n == 3:
            if start == goal:
                print(0)
                continue
            state = (h_cost, start)
            q = [state]
            step = [[[0 for k in range(m_size)] for j in range(m_size)] for i in range(m_size)]
            step[start[0]][start[1]][start[2]] = 1
            pc1, pc2, pc3 = path_cost
            
            while q:
                h_cost, pos = heappop(q)
                p1, p2, p3 = pos
                if pos == goal:
                    print(step[p1][p2][p3] - 1)
                    break
                
                nps1, nps2, nps3 = adj[p1], adj[p2], adj[p3]
                for np1, np2, np3 in product(nps1, nps2, nps3):
                    if step[np1][np2][np3] or \
                    np1 == np2 or np2 == np3 or np3 == np1 or \
                    (p1, p2) == (np2, np1) or (p3, p1) == (np1, np3) or \
                    (p2, p3) == (np3, np2):
                        continue
                    s = step[p1][p2][p3]
                    new_h_cost = s + max(pc1[np1], pc2[np2], pc3[np3])
                    new_state = (new_h_cost, (np1, np2, np3))
                    heappush(q, new_state)
                    step[np1][np2][np3] = s + 1
            continue

solve()