当前位置: 代码迷 >> 数据结构与算法 >> acm题一道,该如何解决
  详细解决方案

acm题一道,该如何解决

热度:450   发布时间:2016-05-23 09:14:04.0
acm题一道
http://acm.zju.edu.cn/show_problem.php?pid=1002

------解决方案--------------------
【解题思路】
1.广度优先搜索:
这题要求最优解,所以还是得用广搜。也就是每次往城市上不断添加一个新碉堡,如果不能放则把这种方案淘汰;如果可以放,则准备在下一步继续在这个方案的基础上放新的碉堡。最后一轮淘汰的方案即是最优解。比如以下图为例,放第一个碉堡可以有13种选择(N*N-障碍物个数):
4 4 4 4
OXOO #XOO OX#O OXOO
OOOO -(1)- OOOO OOOO …… OOOO
XXOO XXOO XXOO XXOO
OOOO OOOO OOOO OOO# 共13种方案

然后往下依次类推,直到不能摆放新的碉堡#才终止。每次摆放一个就计数+1,最终的计数作为问题的输出。

2.约束条件的优化
由于本题有一定的约束条件,即2个碉堡不能同时出现在一条线上,且中间没有障碍物。所以我们需要每次添加新碉堡时,保证摆放满足条件。如果只是单纯的添加,然后将整个城市状态输入到一个函数里进行判断是否满足约束,效率不高(下图)。
4 4
#XOO #X#O
OOOO -> OOOO -> 约束条件 -> 满足条件继续……
XXOO XXOO 函数判断
OOOO OOOO

于是我们可以每次添加新碉堡的同时,将该碉堡同一行和列的所有路.都换成#。这样#的意义就简单了,原来必须保证#的同行列不能再出现#,现在只需保证新的#不在旧的#上即可。如按照上例摆放步骤:
4 4
#XOO #XOO
OOOO -> #OOO
XXOO XXOO
OOOO OOOO 其中#是自动扩张后的添加上去的。

4 4
#X#O #X##
#OOO -> #O#O
XXOO XX#O
OOOO OO#O 其中#是自动扩张后的添加上去的。

此时,剩下的路O即为下一此摆碉堡的可选位置。而无需考虑怎么样使得两个#不在一行或一列上。

当然在写扩张函数的时候也要注意,必须从新加的碉堡坐标开始往四周写#,如果碰到X或边界,则不继续往下写了,如果碰到#则可以跨过#继续写,如下面这种情况:

4 4
OX## OX##
OO#O -> ####
XX#O XX#O
OO#O OO#O

其中#是第二次添加的碉堡,如果碰到旧的#不跨过去继续写#,则我们可以发现第二行最右侧那个#就仍旧表示成O。

3.数据的表示方法
最后我们将要code来实现这棵广度搜索树。但是如果每个结点都保存这么一个矩阵,代价会非常大,于是我采用N*N的字符串来保存,即将如下城市状态表示为:
OXOO
OOOO -> OXOOOOOOXXOOOOOO
XXOO
OOOO

一个N*N的矩阵被平铺为N*N的字符串,便于结点的存储。虽然这样使得碉堡的扩张函数略微难写了点,但基本效率提高了,损失点可读性也是可行的。
  相关解决方案
本站暂不开放注册!
内测阶段只得通过邀请码进行注册!
 
  • 最近登录:Tue Dec 12 20:14:46 CST 2017
  • 最近登录:Tue Dec 12 20:14:46 CST 2017
  • 最近登录:Tue Dec 12 20:14:46 CST 2017
  • 最近登录:Tue Dec 12 20:14:46 CST 2017
  • 最近登录:Tue Dec 12 20:14:46 CST 2017