关灯问题II

题目传送门

解题思路

它的起点是一定的，终点也一定，求最小步数，满足边权都为1，很明显是一道状压BFS

将它的状态存到队列里，一开始全部为1

转移

我们设a[i][j]表示第i个开关可以改变第j个灯
当a[i][j]为1，并且当前状态的第j位为1时，则当前状态为当前状态异或2^j-1次方，即改变第j位上的值为0
当a[i][j]为-1，并且当前状态的第j位为0时，则当前状态为当前状态或2^j-1次方，即改变第j位上的值为1

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,head,tail,c[1<<10],a[105][15],f[1<<10][3];
void bfs()//bfs
{
   
	tail=1;
	f[1][1]=(1<<n)-1;//初值
	c[(1<<n)-1]=1;//标记
	while(head<tail)
	{
   
		head++;
		for(int i=1;i<=m;i++)
		{
   
			int num=f[head][1];//要用个数赋值f[head][1]，不能直接用f[head][1],会改变f[head][1]的值
			for(int j=1;j<=n;j++)
			 if(a[i][j]==1&&(num&(1<<j-1)))
			  num^=(1<<j-1);
			   else if(a[i][j]==-1&&!(num&(1<<j-1)))
			         num|=(1<<j-1);
			if(c[num]==0)
			{
   
				c[num]=1;//标记
				f[++tail][1]=num;//入队
				f[tail][2]=f[head][2]+1;//转移
				if(num==0)
				{
   
					printf("%d",f[tail][2]);//输出
					return;
				}
			}
		}	
	}
	printf("-1");//在
}
int main()
{
   
	scanf("%d%d",&n,&m);//输入
	for(int i=1;i<=m;i++)
	 for(int j=1;j<=n;j++)
	  scanf("%d",&a[i][j]);
	bfs();
	return 0;  
}

谢谢