C语言结合数据结构的硬币游戏

来源：百度知道 编辑：UC知道 时间：2024/06/14 01:28:12
在游戏开始之前，在桌上将三个硬币放置成一条直线。游戏开始的时候，中间一个硬币是背面朝上，其他两个硬币是正面朝上。游戏目标是改变硬币的摆放形式，让中间一个硬币正面朝上，其他两个硬币背面朝上。具体规则如下：
（1） 任何时候都能翻转中间的硬币 （从正面翻成背面或相反）
（2） 当另外两个硬币都是正面或都是背面的时候能够翻转一端的硬币（从正面翻成背面或相反）；
不能通过任何其他方式翻转硬币，如平移它们。但是，只要满足这些规则，你就能够翻转硬币。
（提示：使用无向图，图中每个顶点代表三个硬币的一种状态（8种状态对应8个顶点，一个状态可用一个字符串表示，如”+ - +”表示了一个中间一个硬币是背面朝上，其他两个硬币是正面朝上的状态）；当使用其中一条规则能在两个状态之间来回移动时，就通过一个边连接无向图的两个顶点。该游戏使三个硬币从一种状态改变成另外一种状态，其实就是查找相应两个顶点之间路径的问题，该路径只能沿着边进行。）

/************************************************************
　　每种状态用3位二进制数表示（1为正面，0为背面）
　　目标状态010
　　状态转移
　　000->010/001/100
　　001->011
　　010->110/011/000
　　011->001
　　100->110
　　101->111/001/100
　　110->100
　　111->011/110/101

　　用矩阵表示（0本身，1可达，-1不可达）
　　{ 0, 1, 1,-1, 1,-1,-1,-1},
　　{-1, 0,-1, 1,-1,-1,-1,-1},
　　{ 1,-1, 0, 1,-1,-1, 1,-1},
　　{-1, 1,-1, 0,-1,-1,-1,-1},
　　{-1,-1,-1,-1, 0,-1, 1,-1},
　　{-1, 1,-1,-1, 1, 0,-1, 1},
　　{-1,-1,-1,-1, 1,-1, 0,-1},
　　{-1,-1,-1, 1,-1, 1, 1, 0},
　　*************************************************************/

　　#include <stdio.h>
　　#include <stdlib.h>
　　#include <string.h>
　　char A[8][8]={
　　{ 0, 1, 1,-1, 1,-1,-1,-1},
　　{-1, 0,-1, 1,-1,-1,-1,-1},
　　{ 1,-1, 0, 1,-1,-1, 1,-1},
　　{-1, 1,-1, 0,-1,-1,-1,-1},
　　{-1,-1,-1,-1, 0,-1, 1,-1},
　　{-1, 1,-1,-1,