同一个世界OL 计算机求解

同一个世界

同一个世界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