题目描述

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

输入格式

第一行给出 $W,\ H,\ N$。下面 $W$ 行 $H$ 列给出字符矩阵。

输出格式

最少需要的步数。

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