回 帖 发 新 帖 刷新版面

主题:点灯游戏  最少步   急!急!急!

从屏幕上输入一个整数N,建立N行N列的灯,开始时灯全灭,点击一个灯,其上下左右及本身的状态均改变。要求输出把灯全部点亮的最少步,并输出那个灯被操作过。

#include <iostream>

using namespace std;

typedef unsigned long ul;
const  int MAXROW = 200;
const int MAXCEL = 20;


int Solve(int operation[][MAXCEL], int m, int n);
int main()
{      
      const int m = 10;  //运行时改变此值即可
      
      
      int n = m;
      int operation[m][MAXCEL] = {0};
      int s;
      s = Solve(operation, m, n);
      cout << "n =  " << n<<" s= ";
      cout << s << endl;
      for (int i=0; i<m; i++)
          {
            for (int j=0; j<n; j++)
              cout << operation[i][j] << ' ';
              cout << endl;
           }



}


int Solve(int operation[][MAXCEL], int m, int n)
{
    n=m;  
    const ul max = (~0u) >> (32-n);//max的每一位都是1,是具有n位整数的最大值(二进制数),也表示                                                           所有灯都亮的情况
    ul clicks[MAXROW];//存储灯的”是否操作“信息,每个元素表示一行,该元素的每一位表示一盏灯
    for (ul click = 0; click <= max; click++)
        {
           ul a = 0; //临时变量,用来存储某行的灯最终的”暗亮“情况,
           ul b = 0; //用来存储某行的灯的”暗亮“情况,初始值为0
           ul c = click;//用来存储某行的灯的”是否操作“信息,第一行的初始值为 click
           int i = 0;

           do  //处理1--(n-1)行
              {
                clicks[i] = c;//读入第(i+1)行灯的”是否操作“信息
                        //根据第(i+1)行灯的”是否操作“信息确定该行的灯的”暗亮“情况
                b ^= c;  //影响自身
                b ^= (c << 1) & max; //影响左边的灯
                b ^= (c >> 1) & max; //影响右边的灯
                a = b; //用临时变量a存储该行的灯的”
                b = c; //影响下边的灯,用b表示下一行的灯的”暗亮“情况
                        //根据该行的灯的”暗亮“情况,确定下一行灯的”是否操作“信息暗亮“情况
                c = (a ^ max) & max;
               } while(++i < m - 1);

                  clicks[i] = c; //读入最末行灯的”是否操作“信息
                  //确定最末行灯的”暗亮“情况
                  b ^= c;
                  b ^= (c << 1) & max;
                  b ^= (c >> 1) & max;

                  if (b == max)//如果最末行灯全亮,表示有解
                  {
                        int sum = 0;
                        for (i=0; i<m; i++)
                        {
                              for (int j=n-1; j>=0; j--)
                              {
                                    operation[i][n-j-1] = (clicks[i] >> j) & 1;
                                    if (operation[i][n-j-1] == 1)
                                          sum++;
                              }
                        }
                        return sum;
                  }
            }
      
}
该代码中改m值必须在程序中改,如何改程序,可以在屏幕上输入m的值?

回复列表 (共2个回复)

沙发

玩&amp;quot;东西南北&amp;quot;的最少,玩&amp;quot;南北东西&amp;quot;的最多。

板凳

即然是算法讨论,那就把核心算法标出哦,这样看着很累人的!

我来回复

您尚未登录,请登录后再回复。点此登录或注册