#P1329. The Morning after Halloween小鬼回家
The Morning after Halloween小鬼回家
题目描述
网格上有一些(最多三种)小写字母(鬼),分别移动它们对应的大写字母里。每步可以有多个鬼同时移动,但每步结束之后任何两个鬼不能占用同一个位置,也不能在一步之内交换位置。所有空格连通,所有障碍格连通。任何一个 子网格至少有一个障碍格。
输入格式
输入包含至多 组数据,以 0 0 0 结束。每组第一行给出 ,满足 ,。接下来 行、每行 个字符(空格也是格子)。# 为障碍;小写字母 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