百度追星

                        百度公司在上市之后，开始逐渐在程序员的招聘中出新招了。

文/闫辉

在加入百度任人力资源部总监之前，鲁灵敏曾经在联想、西门子这样的大企业从事过同样的工作，但到了百度他才感受到这个公司对技术人员的需求能如此强烈。在与跨国研发中心，知名软件企业争夺软件人才的过程中，如何才能吸引到足够的优秀程序员和毕业生加入百度，这是他每天都要考虑的问题。即便在百度已经在Nasdaq上市并且吸引了足够多的眼球之后，真正实在的招聘到足够的人才也是一件不容易的事情。

不过，鲁灵敏最近的心情非常好，原因是他们刚刚成功举办了一次“程序之星”的编程大赛。这次活动结束后，几乎每个参赛选手都给他回了热情洋溢的信，而且很多人表示加盟或者推荐自己朋友加入百度的愿望。鲁灵敏表示，“尽管这次活动投入了很大的财力和精力，但收获也非常大，我们将会继续做下去。”

应该说，国外程序大赛并不是少见，比如Google和微软这样的企业都经常通过这种方式来培养潜在的用户，或者从中找到合适的对象。但国内的软件企业在这方面的投入相比比较少，而且往往局限在自己的技术上来进行。百度这次主要面向学校来进行的宣传，但事实上并没有排斥面向社会的含义。

确定要进行程序比赛后，百度工程师就忙碌了起来，他们首先在内部征集考试的问题。这些一线的工程师大概收集了二十道的题目，从中他们又根据一些原则进行了挑选。百度首席架构师周利民说：“我们出题的方向也有自己的想法，首先不会像ACM那样偏重算法，我们要求这个程序是可以运算出结果的，是要解决一个实际的问题。这样的题目不会特别难，但要想做好会很难。这和搜索引擎有些类似，比如搜索引擎大家都可以做，但要做好有无数的地方可以去优化，需要解决问题。也就是很多题不仅要正确，而且还要看性能。”

为了更好的进行选拔，第一步是像“超级女生”那样进行海选。在规定的两天之内所有人都可以登陆到一个固定的网址注册登陆后得到问题和一些样本数据，他可以下载到本地近些年过程序的编写，只要在12小时内将程序提交上来就可以进行判断了。为了更好的体现公平的原则，百度的几位工程师还为此专门开发的一套判卷系统。他可以返回对方的程序能否在系统中编译通过的信息，同时在后台他们还通过一个测试程序来判断程序的运行效率。

百度的北京、上海、广州一些校园和网上进行了一些宣传后，短短两天内，便有近四千名学生进行的问题的解答，这一参赛人数大大超过了百度的预估。而且他们还注意到参赛的选手中还有三名高中生，其中一个还得了满分。。于是他们选择了前三百名选手又进行了第二轮的复赛。经过第一轮四道题目和第二轮两道题目的比赛，最终产生了五十名参加决赛的选手。

不过，由于百度也是第一次举办这样的比赛，其中还出现了一些插曲。在最终结果名单颁布之后，有些选手给他们发来了信件，说明自己肯定题目是做对了，但并没有被选中。后来经过百度工程师的人工查询，发现系统的确在某些方面考虑的还不完善，有些是因为选手的答案格式存在一定问题而没有被系统识别通过。最终他们又从这些选手中选择了七位选手，组成了最后57人的决赛队伍。

决赛在北京举行，为了不影响这些学生的学习，他们选在一个周末来进行考试。鲁灵敏说：“为了更好的节省时间，我们给选手提供了免费双程机票，而且从他们出发的那一刻起到他们回去的时间，我们都给他们购买了意外保险。百度的保险医生三天全程陪同。而且为了更好的管理这些选手，我们分成了小组，每个小组都有一位我们公司的总监带领。”

决赛是在周六的上午在友谊宾馆举行，整个比赛只有一道题目：设计算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用C/C++实现。三个小时的时间对于这些选手来说亲身的感受却稍嫌不同。最终，这道题目有差不多一半的选手答了出来，但性能的差异决定了最终的名词。清华的一位大二的学生获得了第一名，拿走了一万元的奖金，而一位高中生还获得第六名的好成绩。

比赛之后，这些选手和百度的员工进行了深入的交流。对这些选手来说，他们以前可能只是听说过百度，并不一定了解百度的技术和文化，而这样的沟通让他们对百度充满了敬仰。同时百度工程师也惊讶的发现，这些学校的孩子水平真的很高。

不过，这次程序大赛也反映出了一些问题。比如，题目并不是很难，但一些选手做不出来，说明学校教育在动手解决问题方面还存在一定欠缺。周利民说：“我们在招聘研发人员的时候，研究生的比例比较高，也反映了本科生解决问题能力欠缺的问题。”

考试结束后，选手们在百度总监们的带领下，游览了颐和园，晚上吃完巴西烤肉，还参加了一场专门为他们举行的晚会。百度总裁李彦宏虽然因为要出国没有来及参加，但还是专门录制了一段Video向选手问好。

鲁灵敏认为百度举办这次大赛主要的目的是为国内的专业学生和软件开发人员创造了一个沟通的平台。周利民说：“我们希望通过这种活动，可以去激发学生对程序、编程这个领域的追求。另外就是百度比较希望，学生要了解工业界的需求，毕业生真正能够解决一个实际问题，现在他们就需要向这些方向去努力。“

相信未来软件企业的这种类似的活动会越来越多。虽然其中也有企业的宣传需求和招聘，但我们仍然希望这样的活动越来越多，帮我们更好的宣传软件技术的理念，挖掘出更多的开发人才。

总决赛题如下：
 
 题目描述：八方块移动游戏要求从一个含8个数字（用1-8表示）的方块以及一个空格方块（用0表示）的3x3矩阵的起始状态开始，不断移动该空 格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他 位置上有3个方向可移动。例如，假设一个3x3矩阵的初始状态为：
 8 0 3
 2 1 4
 7 6 5
目标状态为：
 1 2 3
 8 0 4
 7 6 5
则一个合法的移动路径为：
 8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3
 2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4
 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5

另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为5。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。 

请设计算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用C/C++实现。 

 输入数据：程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态，这两个文件都由9个数字组成（0表示空格，1-8表示8个数字方块），每行3个数字，数字之间用空格隔开。假定start.txt和goal.txt不会相同。 
 输出数据：如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出-1。请在数字输出后再输出一回车换行符。
 自测用例：如果输入为：start.txt和goal.txt，则产生的输出应为：
5

如果用
7 8 4
3 5 6
1 0 2
替换start.txt中的内容，则产生的输出应为：
21 

如果用
7 5 2
0 6 3
4 1 8
替换start.txt中的内容，则产生的输出应为：
-1 
 评分规则：我们将首先使用10组不同的start.txt和goal.txt进行测试，每个测试用例的运行时间在一台Intel Xeon 2.80GHz 4 CPU/6G 内存的Linux机器上应不超过10秒（内存使用不限制），否则该用例不得分；

每个选手的得分由两部分组成：正确性得分（10秒钟内能产生正确结果的测试用例数量x10）和时间性能得分（10秒钟内产生这些正确结果的测试用 例的平均运行毫秒数）。正确性得分高的将始终比正确性得分低的排名在前，即使前者的平均运行时间比后者的要长；正确性得分相同的将按平均运行时间的快慢排 列。