首页 > ACM题库 > HDU-杭电 > hdu 2622 Everyone is No.1待解决[解题报告]C++
2014
02-12

hdu 2622 Everyone is No.1待解决[解题报告]C++

Everyone is No.1

问题描述 :

Everyone is No.1—— As long as there is belief in my heart, I will hold on until the last moment. Real hero, spirit never die!

See Figure 1, Teddy was in the left-up point, a ‘E’ represents a hole. Now, Teddy want to fill in all the hole. He has a special soil gun. When he shot, it can spread right or down at any time and fill the hole when it get through it, every shot must stop at the right-down point. See figure 2, Teddy should shot three times, but the more optimal solution was in the figure 3.


Figure 1

                  

Figure 2                                     Figure 3

Your task is to create a program that will determine the minimum number shots needed to fill all the hole, if you can’t have any solution about it, don’t fell sorry. Because Everyone is No.1, you can solve other problems first , then return to this problem, you will see it can be so easy.

输入:

The input consists of one or more field maps. A field map consists of two parts:
Firstly, two integers n, m ( 1 <= n, m <= 24)
Secondly, a nXm matrix represent the map.

‘E’ represent the empty hole.
‘.’ represent the soil.

输出:

The input consists of one or more field maps. A field map consists of two parts:
Firstly, two integers n, m ( 1 <= n, m <= 24)
Secondly, a nXm matrix represent the map.

‘E’ represent the empty hole.
‘.’ represent the soil.

样例输入:

6 7
.E.E...
...E.E.
.......
...E..E
.......
.....E.

2 2
EE
EE

样例输出:

2
2


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  4. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢