洛谷2622
思路
定义一个结构体节点，分别存储状态和步骤，状态的某一位是1表示灯开着，是0则表示该灯关，当状态为0000时输出的步骤即为最小步骤。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
int a[120][102]={0};
int vis[1<<11]={0};
int n,m;
struct node
{
int s;
int step;
};
int bfs()
{
queue<node>q;
q.push({(1<<n)-1,0});
//vis[(1<<n)-1]=1;
while(q.size())
{
auto t=q.front();
q.pop();
if(t.s==0)
return t.step;
if(vis[t.s])
{
continue;
}
vis[t.s]=1;
for(int i=1;i<=m;i++)
{
int s=t.s;
for(int j=1;j<=n;j++)
{
if(a[i][j]==1&&s&1<<(j-1))
s^=1<<(j-1);
else if(a[i][j]==-1&&!(s&1<<(j-1)))
s|=1<<(j-1);
}
if(!vis[s])
{
q.push({s,t.step+1});
}
}
}
return -1;
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
cout<<bfs();
}
signed main()
{
cin.tie(NULL);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
solve();
return 0;
}