[USACO23OPEN] Field Day S题解
远古的回忆。
把变换一个字符视为边权为 1 1 1 的边，即求最长路。
最长路不好搞，考虑转补集最短路（容易感性理解），BFS 即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 1e5 + 5;int n, m, a[N], step[1<<18];signed main()
{ios::sync_with_stdio(0); cin.tie(0);memset(step, 0x3f, sizeof(step));cin >> m >> n;int ALL = (1 << m) - 1;queue <int> q;for(int i=1; i<=n; i++){ for(int j=0; j<m; j++){char x; cin >> x; if(x == 'G') a[i] += (1 << j);}step[a[i]] = 0, q.push(a[i]);}while(!q.empty()){int curs = q.front(); q.pop();for(int i=0; i<18; i++){int news = curs^(1<<i);if(step[news] > step[curs] + 1)step[news] = step[curs] + 1, q.push(news);}}for(int i=1; i<=n; i++)cout << m - step[ALL-a[i]] << "\n";
}