USACO2023 US Open Silver P2 Field Day 图论多源BFS

#include <bits/stdc++.h>

using namespace std;

vector<int> dis(1<<18,-1);

vector<int> teams;

queue<int> qi;

int n,c;

void bfs(){

while(!qi.empty()){

int t=qi.front();

qi.pop();

int k=1;

for(int i=0;i<c;i++){

int nx=t^k;

if(dis[nx]<0){

dis[nx]=dis[t]+1;

qi.push(nx);

}

k<<=1;

}

}

}

int main(){

cin>>c>>n;

for(int i=0;i<n;++i){

int t=0,k=1;

string s;

cin>>s;

for(int j=0;j<c;j++){

if(s[j]=='H'){

t=t+k;

}

k=k<<1;

}

teams.push_back(t);

int rev=(1<<c)-1-t;

dis[rev]=0;

qi.push(rev);

       //cout<<i<<" "<<t<<" "<<rev<<endl;

}

bfs();

   //for(int i=0;i<(1<<c);i++){

   //    cout<<i<<" "<<dis[i]<<" : ";

   //}

   //cout<<endl;

for(int i=0;i<n;i++){

cout<<c-dis[teams[i]]<<endl;

}

return 0;

}