点灯best.cpp

一些c++小程序

#include<iostream.h>
const int sizes=25;
int ch[sizes*sizes],sums=0,p[sizes+2][sizes+2];
int in(int x,int y,int size)
{
	return x>0&&x<size+1&&y>0&&y<size+1;
}
int isok(int x,int y,int size)
{
	if(!in(x,y,size))//不在范围内
		return 0;
	 if(in(x-1,y-1,size)&&p[x-1][y-1]==0||in(x,y-1,size)&&p[x][y-1]==1)//范围内左上角或上面不合格
		 return 0;
	       return 1;
}
void  getpath(int n,int &num,int size)
{
	if(n>=(size+2)*(size+1)-1)
	{
	   int sum=0;
	  for(int m=1;m<size+1;m++)
		  for(int n=1;n<size+1;n++)
			  sum+=p[m][n];
		if(sum>=size*size)//判断是否所有灯被点亮
		{
		for(int i=0;i<num;i++)
			cout<<"第 "<<i+1<<"步:( "<<ch[i]%(size+2)-1<<" , "<<ch[i]/(size+2)-1<<" )"<<endl;
		         cout<<"----------------"<<endl;
				   sums++;
		}
	}
	else
	{   
		int x=n%(size+2),y=n/(size+2);//网格坐标
		 if(in(x,y,size))
		 {
			 if(isok(x,y,size))//符合点亮要求
			 {
					 p[x][y]=1-p[x][y];p[x+1][y]=1-p[x+1][y];p[x][y+1]=1-p[x][y+1];p[x-1][y]=1-p[x-1][y];p[x][y-1]=1-p[x][y-1];
					  ch[num]=n;
					   num++;
					    getpath(n+1,num,size);
						  num--;
						   p[x][y]=1-p[x][y];p[x+1][y]=1-p[x+1][y];p[x][y+1]=1-p[x][y+1];p[x-1][y]=1-p[x-1][y];p[x][y-1]=1-p[x][y-1];
						     if(y==1)//如果是第一行
						       getpath(n+1,num,size);
			 }
			 else
				 if(p[x][y-1]==1&&(p[x-1][y-1]==1&&in(x-1,y-1,size)||!in(x-1,y-1,size)))
			    	getpath(n+1,num,size);
		 }
		 else
			 getpath(n+1,num,size);//跳过网格四周的围墙
	}
}
void  main()
{
 int size;
   cout<<"请输入灯的阶数!"<<endl;
     cin>>size;
	  if(size<=sizes&&size>0)
	  {
	      int num=0,begin=size+3;//size+2是给网格加上围墙
	         for(int i=0;i<size+2;i++)
		       for(int j=0;j<size+2;j++)
			       p[i][j]=0;
		        getpath(begin,num,size);
		           cout<<"一共有:"<<sums<<"种简洁解法!"<<endl;
	  }
	  else
		  cout<<"点亮的阶数太大或非正整数,需要较长时间,要得到结果请修改源程序!"<<endl;
}