主题:点灯游戏 最少步 急!急!急!
从屏幕上输入一个整数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的值?
#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的值?