同一个世界OL 计算机求解
同一个世界OL引入了世界关卡，也就是玩家自主设计关卡，其他的玩家来破解。
不像同一个世界，游戏关卡都很对称，比较简单，世界关卡里面有一些很难的关卡。
我写了个程序来破解关卡，不过水平有限，6行5列的关卡大概会需要10秒钟，再大一点的关卡就基本上算不出来了。
思路：
从一个起点出发，使用深度优先搜索，列出所有可能的路径，利用状态压缩把一条路径映射到1个64位的整数。
另外一个起点也是同样处理，这样就得到2个差不多大小的集合S1、S2
然后遍历S1中的元素，和需要得到的最终结果进行1次位运算直接得到需要的另一条路径，然后查找S2是否包含此路径
代码：
-
#include<iostream>
-
#include<set>
-
using namespace std;
-
#define ll long long
-
-
const ll r = 6, c = 5; //需要手动修改
-
int x1 = 0, yy1 = 2, x2 = 5, y2 = 1, result = 20882777; //需要手动修改
-
int has[r][c] = //需要手动修改
-
{
-
1, 1, 1, 1, 1,
-
1, 0, 1, 1, 1,
-
1, 1, 1, 1, 1,
-
1, 1, 1, 1, 1,
-
1, 1, 1, 1, 1,
-
1, 1, 1, 1, 1
-
};
-
-
int num[r][c];
-
set<pair<ll, pair<int, int>>>se;
-
set<ll>se1, se2;
-
-
-
bool ok(int x, int y)
-
{
-
if (x < 0 || x >= r)return false;
-
if (y < 0 || y >= c)return false;
-
if (num[x][y])return false;
-
return has[x][y];
-
}
-
-
void dfs(int x, int y)
-
{
-
num[x][y] = 1;
-
ll res = 0;
-
for (int i = 0; i < r; i++)for (int j = 0; j < c; j++)res = res * 2 + num[i][j];
-
int si = se.size();
-
se.insert(make_pair(res, make_pair(x, y)));
-
if (si < se.size())
-
{
-
if (ok(x + 1, y))dfs(x + 1, y);
-
if (ok(x - 1, y))dfs(x - 1, y);
-
if (ok(x, y + 1))dfs(x, y + 1);
-
if (ok(x, y - 1))dfs(x, y - 1);
-
}
-
num[x][y] = 0;
-
}
-
-
void out(ll n)
-
{
-
ll k = 1 << (r*c);
-
for (int i = 0; i < r; i++)
-
{
-
for (int j = 0; j < c; j++)
-
{
-
k /= 2;
-
if (n&k)cout << "●";
-
else cout << "○";
-
}
-
cout << endl;
-
}
-
cout << endl;
-
}
-
-
int main()
-
{
-
se.clear();
-
se1.clear();
-
se2.clear();
-
for (int ii = 0; ii < r; ii++)for (int jj = 0; jj < c; jj++)num[ii][jj] = 0;
-
dfs(x1, yy1);
-
set<pair<ll, pair<int, int>>>::iterator it;
-
for (it = se.begin(); it != se.end(); it++)se1.insert(it->first);
-
se.clear();
-
for (int ii = 0; ii < r; ii++)for (int jj = 0; jj < c; jj++)num[ii][jj] = 0;
-
dfs(x2, y2);
-
for (it = se.begin(); it != se.end(); it++)se2.insert(it->first);
-
set<ll>::iterator it1;
-
for (it1 = se1.begin(); it1 != se1.end(); it1++)
-
if (se2.find((*it1) ^ result) != se2.end())
-
{
-
out(*it1);
-
out((*it1) ^ result);
-
return 0;
-
}
-
ll temp = 1;
-
for (int i = r - 1; i >= 0; i--)for (int j = c - 1; j >= 0; j--)
-
result -= has[i][j] * temp, temp *= 2;
-
result *= -1;
-
for (it1 = se1.begin(); it1 != se1.end(); it1++)
-
if (se2.find((*it1) ^ result) != se2.end())
-
{
-
out(*it1);
-
out((*it1) ^ result);
-
}
-
return 0;
-
}
使用说明：
代码中有3行标注了 //需要手动修改 ，一共7个整数和1个数组，运行之前根据关卡的实际情况进行修改即可
然后运行即可得到答案。
示例：
一共6行5列，俩起点的坐标分别是（0,2）（5,1），
接下来把颜色信息表示出来，黄色和白色随便哪个对应1，另外一个对应0，空的地方一定是对应0
也就是上图可表示为111110010000010101101010100110或者000001001111101010010101011001
然后把上述两个二进制整数转换成十进制，可以利用http://tool.oschina.net/hexconvert
至此，一共得到7个整数，分别是6,5,0,25,1,1044470438或20882777，依次写到代码里面
最后还有一个has数组，就是用1表示有点（不管颜色），0表示空的地方
如此就完成了代码
运行结果：
由白色的实心圆构成的路径就是我们需要的答案了
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/82528855
- 点赞
- 收藏
- 关注作者
评论（0）