今天朋友发了一张游戏截图（下图），让我帮忙想，实在是没做出来，打算用代码蛮力解决一下。
规则大致有：
- 倒出颜料的试管只能从最顶层开始倒
- 被倒入的试管必须是：1.空，2.最上层颜色与倒入颜色一致
- 每根试管最终都仅一种颜色（或空），游戏结束
思路：
试管是明显的先进后出结构，所以采用栈结构，采用C++标准库的stack，在选择试管时，可能会选到任意两个试管，所以这里我选择了vector，存储num个试管，
过程如下：
先建立Bottle类：
class Bottle {
public:
stack<int> bottle;
public:
Bottle(vector<int> num) {
for (int i : num) {
if (i == 0) break;//0代表空
bottle.push(i);
}
}
~Bottle() {
}
int gettop() {
if (getsize() == 0) return 0;
return bottle.top();
}
void dopush(int num) {
bottle.push(num);
}
void dopop() {
bottle.pop();
}
int getsize() {
return bottle.size();
}
bool iscomplete(){
//判断该试管是否已完成或为空
//用于判断这个试管是否需要再移出颜料
if (getsize() == 0) return true;
if (getsize() < 4) return false;
stack<int> temp = bottle;
int color = temp.top();
while (temp.size() > 0) {
if (temp.top() != color) return false;
temp.pop();
}
return true;
}
bool isonecolor() {
//判断该试管是否只有一种颜色
if (getsize() == 0) return true;
if (getsize() == 4) return false;
stack<int> temp = bottle;
int color = temp.top();
while (temp.size() > 0) {
if (temp.top() != color) return false;
temp.pop();
}
return true;
}
};
上述的部分成员函数是在后续中慢慢补充的，然后是初始化的步骤：
void initialize(int num, vector<Bottle> &bottles)
{
//要动这里的话，必须修改全局变量colorlist
cout << "所有颜色：青绿、褐绿、墨绿、粉色、红色、紫色、蓝色、浅蓝、橘色、黄色、褐色、灰蓝" << endl;
cout << "对应编号：01、 02、 03、 04、 05、 06、 07、 08、 09、 10、 11、 12 " << endl;
cout << "输入每个试管的颜色，若空输0" << endl;
//初始化
for (int i = 1; i <= num; i++) {
vector<int> temp = {};
cout << "输入第" << i << "个试管的颜色编号（从下往上,空格隔开）： ";
int j = 0;
while (j < 4) {
int temp_num = 0;
cin >> temp_num;
if (temp_num == 0) {
temp.push_back(temp_num);
break;
}
temp.push_back(temp_num);
j++;
}
//可以增加一步输入检查:1.是否有四个数字，每个数字是否合法
Bottle *bi = new Bottle(temp);
bottles.push_back(*bi);
}
cout << "每个试管的颜色为（从上往下）：" << endl;
int j = 1;
for (auto i : bottles) {
cout << "第" << j << "个试管的颜色： ";
cout << i << endl;
j++;
}
}
这里对所有颜色做了编号，然后赋值到每个试管对象，并输出最终结果，这里需要重载<<运算符，重载的代码如下：
ostream& operator<<(ostream& cout, Bottle b) {
stack<int> s = b.bottle;
if (s.size() == 0) {
cout << "空";
}
while (s.size() > 0) {
cout << colorlist[s.top()-1]<<" ";
s.pop();
}
return cout;
}
在完成了初始化后，需要开始具体的计算了，本笨蛋解法是蛮力解法，所以直接用的遍历递归的思路，i=1：num，j=1:num，在实现了一次i号到j号后，再对当前情况做求解，若无解就回滚一次，若有解就直接输出最终结果。
void solution(vector<Bottle> &bottles, stack<vector<int>> &solu,int num,int laststep) {
if (doneall(bottles)) return;
vector<int> onestep;//共4位，第一位记录选中试管，第二位记录目标试管，第三位记录颜色编号，第四位记录移动数目
//从i管移到j管
for (int i = 0; i < num;i++) {
if (bottles[i].iscomplete()) continue;//i若已完成，则不能再移动
if (i == laststep) continue;//上一次接受的管子，这次不能再移出
for (int j = 0; j < num; j++) {
if (i == j) continue;//不做自己对自己移动的操作
if (bottles[j].getsize()==4) continue;//j管为4则不能接受
if (bottles[j].getsize() == 0 && bottles[i].isonecolor()) continue;//纯色不允许移到空管
onestep = movecount(bottles, i, j);
if (onestep[3] == 0) continue;//移动数目为0，跳过
solu.push(onestep);
moveonestep(bottles, onestep);
if (doneall(bottles)) return;
solution(bottles, solu,num,j);
if (doneall(bottles)) return;
backonestep(bottles, onestep);
solu.pop();
}
}
}
形参表说明
- vector &bottles：全部试管数据
- stack<vector> &solu：每一步答案的合集
- int num：试管数
- int laststep：上一次操作中，接受颜料的试管编号
其中，laststep是为了避免试管接受后要挪出，造成死循环
其他函数说明，doneall函数用于判断是否已解决，代码如下：
bool doneall(vector<Bottle> bottles) {
for (auto i : bottles) {
if (!i.iscomplete()) return false;
}
return true;
}
movecount函数用于求解当前i到j是否可行，若可行的话，具体移动内容如何，代码如下
vector<int> movecount(vector<Bottle> bottles, int num1,int num2) {
//num1的试管移到num2
int color = bottles[num1].gettop();
vector<int> onestep = { -1,-1,-1,0 };
if (bottles[num2].gettop() != color&& bottles[num2].getsize()!=0) return onestep;
bottles[num1].dopop();
onestep[0] = num1;
onestep[1] = num2;
onestep[2] = color;
onestep[3]++;
while (bottles[num1].gettop() == color&& bottles[num2].getsize()+ onestep[3]<=4) {
onestep[3]++;
bottles[num1].dopop();
}
return onestep;
}
moveonestep函数和backonestep函数用于前进和回滚，所以这两步中间也需要判断一下是否可行，不可能才需要回滚，可行的话直接return，代码如下：
void moveonestep(vector<Bottle> &bottles, vector<int> onestep) {
for (int i = 0; i < onestep[3]; i++) {
bottles[onestep[1]].dopush(onestep[2]);
bottles[onestep[0]].dopop();
}
}
void backonestep(vector<Bottle> &bottles, vector<int> onestep) {
for (int i = 0; i < onestep[3]; i++) {
bottles[onestep[0]].dopush(onestep[2]);
bottles[onestep[1]].dopop();
}
}
最后主函数
int main(int argc, char *argv[])
{
int num = 0;
cout << "输入总试管数：";
cin >> num;
vector<Bottle> bottles;
initialize(num, bottles);
stack<vector<int>> solu;
solution(bottles, solu,num,-1);
stack<vector<int>> solu2;
while (solu.size()!=0) {
solu2.push(solu.top());
solu.pop();
}
while (solu2.size() != 0) {
auto i = solu2.top();
cout <<"从"<< i[0]+1 <<"移动到"<< i[1]+1 <<"，移动颜色为："<< colorlist[i[2]-1] <<"，移动数目为："<< i[3] << endl;
solu2.pop();
}
cout << "最终结果，每个试管的颜色为（从上往下）：" << endl;
int j = 1;
for (auto i : bottles) {
cout << "第" << j << "个试管的颜色： ";
cout << i << endl;
j++;
}
return 0;
}
实现过程中发现的bug：
- 会出现一种单色试管的颜料来回在空试管之间震荡的情况，用isonecolor函数解决
- 出现试管初始颜料块不足4个的情况（1/2/3个），增加判断条件解决
全部代码见我的github。
可以继续改进的地方：
- 可视化，做更便捷的做输入。
- solution函数太傻了，在获得结果后还要一层层return出来。
- 蛮力算法太耗时，算法层面上应该要有更高级的解法。
