#include
#include
#include
#define MR 32 // 理论上这个程序可以运算的数字大于32但受无符号长整型位数限制只能构造出32*32的数组
#define MJNUM 20
typedef struct _LightMatrix
{
unsigned long mtrx[MR]; //定义无符号长整型的能到达的最大的宽度的数组
int width;
int height; //本程序中的长和宽是相等的
}LightMatrix;
void PrintLine(unsigned long line,int width)//输出一行
{
int i=0;
unsigned long mark=1;
for(i=width-1;i>=0;--i)
{
putchar((line& (mark<<i)) ?'*':'-');
}
printf("\n");
}
void ProcessRow(LightMatrix*m,int r_num,unsigned long r_mode)
{
unsigned long mask;
int i=0;
for(i=0; iwidth; ++i)
{
mask=1<
if((r_mode&mask) !=0)
{
if(r_num>0) m->mtrx[r_num-1]^=mask;
if(r_num+1height) m->mtrx[r_num+1]^=mask;
mask=mask | (mask<<1) | (mask>>1);
m->mtrx[r_num]^=mask;
}
}
}
void Solve(LightMatrix*m,LightMatrix** result_list) //这是求解函数
{
unsigned long i=0;
int j=0;
int total_count=(int)pow(2,m->width); //共需枚举的次数2的宽度值次方
int counter=0;
LightMatrix* result= (LightMatrix*)malloc(sizeof(LightMatrix));
result->width=m->width;
result->height=m->height;
for(i=0; i<total_count; ++i) //枚举第一行的情况
{
memset(m->mtrx,0,sizeof(m->mtrx));
result->mtrx[0]=i;
ProcessRow(m,0,result->mtrx[0]); //处理第一行
for(j=1; j<m->height; ++j)
{
result->mtrx[j]=~(m->mtrx[j-1]); //根据上一行处理当前行，既用下一行把不亮的灯点亮
ProcessRow(m,j,result->mtrx[j]);
}
unsigned long mark=~0ul<<m->width; //0UL 表示 无符号长整型 0这句话啥意思特别是 ~ 这个符号
if((m->mtrx[m->height-1] | mark) ==~0ul) //判断最后一行是否全为 1，即若是全1方案可行，否则丢弃。
{
result_list[counter++]=result; //重新分配一个解的空间
result= (LightMatrix*)malloc(sizeof(LightMatrix));
result->width=m->width;
result->height=m->height;
if(counter+1>MJNUM) break;//解
}
}
}
void Solution(LightMatrix*result)
{
int i=0;
for(i=0; iheight; ++i)
{
PrintLine(result->mtrx[i],result->width);
}
}
int main(void)
{
LightMatrix m;
LightMatrix* results[MJNUM+1]={NULL};
int w=0,h=0;
int i=0;
printf("请输入你要点灯方阵的边长（小于等于32） \n");
scanf("%d", &w);
m.width=w;
m.height=w;
Solve(&m,results);
if(results[0]!=NULL) //判断是否有解函数
{
while(results[i]!=NULL)
{
Solution(results[i]);printf(""); //如果有解输出所有解的情况。
printf(" \n");
i++;
} printf("以上即点灯方法，一共有%d个解\n",i);
}
else
{
printf("对不起，此情况无解");
}
}
