P2622

普通的bfs，然后就位运算乱搞，结果有几个点答案都多个1，是我这个算法哪里有问题吗

70pts:

#include<bits/stdc++.h>
#define N 20
#define M 110
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
/*-----------------------OI使我快乐---------------------------*/
int n,m;
int eff[M][N];
queue <int> q;
int f[5500];
bool vis[5500];
void bfs()
{
    q.push(0);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    vis[0]=1;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        int temp;
        for(int i=1;i<=m;++i)
        {
            temp=u;
            for(int j=1;j<=n;++j)
            {
               if(eff[i][j] == 1)
               {
                   temp = temp ^ (1 << (j - 1));
               }else if(eff[i][j] == (-1))
               {
                   temp = temp  & (~(1 << (j - 1))); 
               }else{
            
               }
            }
            //cout<<"Past:"<<u<<" "<<"Nw:"<<i<<" "<<temp<<endl;
            if(vis[temp]) continue;
            vis[temp]=1;
            f[temp]=f[u]+1;
            q.push(temp);
            if(temp == (1 << n)-1)
            {
                write(f[temp]);
                cout<<endl;
                system("pause");
                exit(0);
            } 
        }
    }
    write(-1);
}
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)
            eff[i][j]=read();
    bfs();
    cout<<endl;
    system("pause");
    return 0;
}