蓝桥杯 C\C++ 组题目: 纵横放火柴游戏 - sbw Blog

蓝桥杯 C\C++ 组题目: 纵横放火柴游戏

来源: 石博文博客 | 浏览: 3106 | 评论: 2 发表时间: 2013-06-19

蓝桥杯算法大赛中C/C++组题目: 纵横放火柴游戏.在3x4的格子中,游戏的双方轮流放置火柴棒,其规则是:1. 不能放置在已经放置火柴棒的地方(即只能在空格中放置)。2. 火柴棒的方向只能是竖直或水平放置。3. 火柴棒不能与其它格子中的火柴“连通”。所谓连通是指两根火柴棒可以连成一条直线,且中间没有其它不同方向的火柴“阻拦”。 4. 游戏双方轮流放置火柴,不可以弃权,也不可以放多根。直到某一方无法继续放置,则该方为负(输的一方)。游戏开始时可能已经放置了多根火柴。本文给出了此题的C++解法.



这是一个纵横火柴棒游戏。如图,在3x4的格子中,游戏的双方轮流放置火柴棒。其规则是:


示意图

1. 不能放置在已经放置火柴棒的地方(即只能在空格中放置)。


2. 火柴棒的方向只能是竖直或水平放置。


3. 火柴棒不能与其它格子中的火柴“连通”。所谓连通是指两根火柴棒可以连成一条直线,且中间没有其它不同方向的火柴“阻拦”。


例图所示的局面下,可以在C2位置竖直放置(为了方便描述格子位置,图中左、下都添加了标记),但不能水平放置,因为会与A2连通。同样道理,B2,B3,D2此时两种方向都不可以放置。但如果C2竖直放置后,D2就可以水平放置了,因为不再会与A2连通(受到了C2的阻挡)。


4. 游戏双方轮流放置火柴,不可以弃权,也不可以放多根。直到某一方无法继续放置,则该方为负(输的一方)。


游戏开始时可能已经放置了多根火柴。


你的任务是:编写程序,读入初始状态,计算出对自己最有利的放置方法并输出。


如图的局面表示为:


00-1

-000

0100


即用“0”表示空闲位置,用“1”表示竖直放置,用“-”表示水平放置。


输入、输出格式要求:


用户先输入整数 n(n<100), 表示接下来将输入 n 种初始局面,每种局面占3行(多个局面间没有空白行)。


程序则输出:每种初始局面情况下计算得出的最佳放置法(行号+列号+放置方式)。


例如:用户输入:


2


0111

-000

-000

1111


----

0010


则程序可以输出:


00-

211

不难猜出,输出结果的含义为:


对第一个局面,在第0行第0列水平放置,对第二个局面,在第2行第1列垂直放置


注意:


行号、列号都是从0开始计数的。


对每种局面可能有多个最佳放置方法(解不唯一),只输出一种即可。


例如,对第一个局面,001 也是正解;最第二个局面,201也是正解。


题目分析

两人轮流下子,当对方不能再下子,就赢了,这是一个博弈的问题,一般都是用堆栈来做,向栈中放入下一个可以下子的节点,当放不下时,弹出2个节点(每人悔棋1步),再尝试重新下子,当栈中节点数量为0时,说明此时第一个下子的人完胜(此时为第二个人无法下子的回溯),因为此时第二个人无论下什么自己都不会死,得解.若栈中节点数量为1,说明此时为自己死,那么可以尝试下下一个可以下子的位置,若遍棋盘也没有可下子的位置,则说明自己不可能羸.


另注:

在本题的测试用例中,有一处错误,第一个测试用例的第二种情况测试答案有错,答案给的是201,分析如下:


对于这个例子,先下子的A不可能羸,即不存在题目说的'最优',而我的程序会直接输出'不可能羸'


纵横放火柴游戏的 C++ 语言解法

函数解释:

bool check(const node& n,const string& map); 用来检查当前最后一个子的位置是否违反游戏规则.


void changeNext(node& n,string& map); 将最后一个子的下子情况进行下一级尝试.


void addNode(vector& data,string& map); 为栈中增加一个节点(即再走一步).


string getResult(string map); 算法的主函数,核心算法为栈+回溯.


算法效率:

因为计算量很小,执行速度很快,不需要额外优化.




  • 声明: 评论属于其发表者所有,不代表本站的观点和立场.
  • lvv2.com 回复该留言 时间: 2013-06-20

    多谢分享,,旅途新热榜--互联网热点榜单!观光团,围观。。博主。。

已有 1 位网友发表了一针见血的评论,你还等什么?
  • 昵称: *
  • 邮箱:
  • 网址:
  • 记住我的信息
  • Color
  • Red
  • Blue
  • Code
  • bash
  • cpp
  • css
  • java
  • js
  • perl
  • php
  • python
  • ruby
  • sql
  • xml