#P1329. The Morning after Halloween小鬼回家

    ID: 341 传统题 1000ms 512MiB 尝试: 38 已通过: 13 难度: 6 上传者: 标签>CF1900普及+/提高-双向 BFS状态编码状态去重分层扩展预计算转移

The Morning after Halloween小鬼回家

题目描述

w×hw\times h 网格上有一些(最多三种)小写字母(鬼),分别移动它们对应的大写字母里。每步可以有多个鬼同时移动,但每步结束之后任何两个鬼不能占用同一个位置,也不能在一步之内交换位置。所有空格连通,所有障碍格连通。任何一个 2×22\times 2 子网格至少有一个障碍格。

输入格式

输入包含至多 1010 组数据,以 0 0 0 结束。每组第一行给出 W,H,NW,H,N,满足 4≤W,H≤164\le W,H\le16,1≤N≤31\le N\le3。接下来 HH 行、每行 WW 个字符(空格也是格子)。# 为障碍;小写字母 a,b,c 为起点,对应大写字母为终点。最外围全部为障碍。保证存在合法的回家方案。

输出格式

对每组数据输出一行,表示最少需要的步数。

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