Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
125703 | mairuisheng | 翻转棋盘2 | C++ | 通过 | 100 | 27 MS | 268 KB | 1094 | 2024-01-23 21:30:53 |
#include <bits/stdc++.h> using namespace std; int n; int a[107],b[107],cur[107],change[107]; int cal(int num){ int ans = 0; while(num){ ans++; num &= num-1; } return ans; } int sol(int a[]){ int ans = ~(1<<31); for(change[0] = 0;change[0]<(1<<n);change[0]++){ int sum = 0; cur[0] = a[0]; for(int i = 0;i<n;i++){ sum += cal(change[i]); cur[i] = cur[i] ^ change[i] ^ (change[i]>>1) ^ ((change[i]<<1)&((1<<n)-1)); cur[i+1] = a[i+1] ^ change[i]; change[i+1] = cur[i]; } if(!cur[n-1]) ans = min(ans,sum); } return ans; } int main(){ std::ios::sync_with_stdio(0); cin>>n; for(int i = 0;i<n;i++){ for(int j = 0;j<n;j++){ char tmp; cin>>tmp; if(tmp == 'b') a[i] |= (1<<j); else if(tmp == 'w') b[i] |= (1<<j); } } int ans = min(sol(a),sol(b)); if(ans>n*n) cout<<"Impossible"<<'\n'; else cout<<ans<<'\n'; return 0; }