网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[NOIP2010冲刺三]鬼屋惊魂
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | jumby.in | 输出文件 | jumby.out |
【题目描述】
要求你写一个程序,在一个地图中,找到最小步数将每个鬼移动到他们指定的位置。地图包含一些小方格。每格要么是墙(鬼不能进入),要么是走廊(鬼能进入)。
每一步里,你可以同时移动任意数量的鬼。每个鬼要么待在原地不动,要么移动到相邻的格子里(相邻的格子有公共边),如果移动满足下列条件,则移动是可行的。
1. 没有一个以上的鬼在同一个格子里。
2. 没有一对鬼在一步里交换了位置。
例如,假设鬼的位置是如右上图所示的,其中 sharp(#) 表示墙,空格表示走廊, a , b , c 表示鬼:
####
ab#
#c##
####
经过一步移动过后,地图可以变成如下的样子:
#### #### #### ####
ab# a b# acb# ab #
#c## #c## # ## #c##
#### #### #### ####
【输入格式】
输入包括最多 10 组数据,每组数据包含一幅地图。输入格式如下:
第一行的 w , h 和 n 表示地图的宽度和高度, n 表示鬼的数目,他们满足:
4 ≤ w ≤ 16, 4 ≤ h ≤ 16, 1 ≤ n ≤ 3
接下来 h 行,每行 w 个字符:
一个 # 表示墙。
一个小写字母表示鬼的初始位置(该位置也是走廊)。
一个大写字母表示鬼的目标位置(该位置也是走廊)。
一个空格表示空的走廊。
在每幅地图里,前 n 个小写字母和前 n 个大写字母表示鬼的初始位置及鬼的目标位置。我们需要将小写字母表示的鬼移动到对应的大写字母的位置里。
最后一组数据后一行有三个 0 。
【输出格式】
对每组数据输出一行一个整数,表示最小的移动步数。
【输入样例】
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