游戏:
简单的DFS搜索。
这个代码一个缺点是要倒着看,另一个缺点是有两个瓶子装着同一种颜色并且可以操作时,如果在它们前面还有一个空瓶子时,会先倒进空瓶子,再倒进该倒进的瓶子。
最后一个缺点是过于暴力,毫无策略(反正人类玩的十来个瓶子的场景肯定没问题)。
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int N, max_Volunm, not_empty;
vector<vector<int>> scene;
void printScene(vector<vector<int>> s) {
for (int i = max_Volunm - 1; i >= 0; i--) {
for (int j = 0; j < N; j++) {
if (s[j].size() <= i)
cout << "- ";
else
cout << s[j][s[j].size() - i - 1] << " ";
}
cout << endl;
}
}
bool checkState() {
for (auto s : scene)
{
if (s.size() == 0)
continue;
if (s.size() < max_Volunm)
return false;
int c = s[0];
for (auto c_in_s : s) {
if (c_in_s != c)
return false;
}
}
printScene(scene);
return true;
}
bool getResult() {
if (checkState())
return true;
for (int i1 = 0; i1 < scene.size(); i1++) {
auto& s1 = scene[i1];
if (s1.size() == 0)
continue;
for (int i2 = 0; i2 < scene.size(); i2++) {
auto& s2 = scene[i2];
if (s1 == s2)
continue;
if (s2.size() == 0 || *(s1.begin()) == *(s2.begin()))
{
auto old_scene = scene;
auto old_s1 = s1, old_s2 = s2;
int same_color = *(s1.begin());
bool flag = true;
reverse(s2.begin(), s2.end());
while (s1.size() > 0 && *(s1.begin()) == same_color) {
if (s2.size() >= max_Volunm) {
flag = false;
break;
}
s1.erase(s1.begin());
s2.push_back(same_color);
}
reverse(s2.begin(), s2.end());
if (s2 != old_s1 && s1 != old_s2 && flag && getResult()) {
cout << i1 << "->" << i2 << endl;
printScene(old_scene);
return true;
}
scene = old_scene;
}
}
}
return false;
}
int main()
{
cin >> N >> max_Volunm>>not_empty;
scene.resize(N);
for (int i = 0; i < not_empty; i++) {
for (int j = 0; j < max_Volunm; j++) {
int in;
cin >> in;
scene[i].push_back(in);
}
}
getResult();
while (true);
}