1.18　挖雷游戏

挖雷（Minesweeper）游戏很受Windows用户的喜爱，它的游戏规则很简单，盘面上有数字标明周围地雷的数量，游戏者根据数字提示，清除没有地雷的方块，标出盘面上的所有地雷即可，如图1-34所示。

图1-34

这样一个“古老”的游戏，有什么可以挖掘的呢？

问题1：如果用户想为这个“古老”的游戏增加一个新功能，即按一个功能键，就能看到剩余所有未标识的方块是否有地雷的概率。你能否实现这一功能？

问题2：如果上一个问题太难了，可以让程序先标识所有肯定有地雷的方块。

注释

①　作者注：当面试的同学听到这个问题的时候，很多人都有点意外。我把我的笔记本电脑交给他们说，这是开卷考试，你可以上网查资料，干什么都可以。大部分面试者在电脑上的第一个动作就是上网搜索“CPU控制50％”这样的关键字，当然没有找到什么直接的结果。不过这本书出版以后，情况可能就不一样了。

②　如果应聘者从来没有琢磨过任务管理器，那还是不要在简历上说“精通Windows”为好。

③　例如WaitForSingleObject()。

④　可以通过Sleep()来实现。

⑤　这一题目由微软亚洲研究院工程师Matt Scott提供，他在学习中国象棋的时候想出了这个题目，后来一位应聘者给出了比他的“正解”简明很多的答案，他们现在成了同事。

⑥　Gates，W. and Papadimitriou，C. "Bounds for Sorting by Prefix Reversal." Discrete Mathematics. 27，47～57，1979．据说这是Bill Gates发表的唯一学术论文。

⑦　这是我们为了计算的方便而制定的价钱，不保证8欧元可以买到这样的书。

⑧　如果各种饮料数量都无限的话，这种方法是很简单。但是如果饮料有个数限制，复杂度可能达到指数级，您有更好的办法么？

⑨　CS：英文名称：Half-life或者Counter-Strike，一种风靡全球的第一人称动作类枪战游戏。

⑩　在设计中，曲线也可以用一组直线来模拟以简化模型，加快速度。

⑪　关于在不同平台上进行多线程的通讯的详细技术细节，请参考相应的SDK和API说明。

⑫　温馨提示：你还记得教我们XOR运算的老师么？这门课一定比较枯燥吧，如果当时能玩NIM这个游戏就好了。

⑬　提一句，这是一个不明智的分堆办法，不如分为（6，6），这样必赢无疑。

⑭　究竟有多少不一样的数独排列，请看“数独知多少”一节。