关灯问题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;
}