提交时间:2024-03-06 13:17:25
运行 ID: 135691
#include <bits/stdc++.h> #define int long long using namespace std; int c[5][5],minn = 9e18,dx[] = {0,1,0,-1},dy[] = {1,0,-1,0}; void dfs(int x,int ans){ if (x == 17){ int s = 0; for (int i = 1; i <= 4; i++)for (int j = 1; j <= 4; j++)s += c[i][j]; if (s == 0 || s == 16) minn = min(minn,ans); return; } dfs(x + 1,ans); int i = (x - 1) / 4 + 1,j = (x % 4)?(x % 4):4; c[i][j] ^= 1; for (int k = 0; k < 4; k++){ int tx = i + dx[k],ty = j + dy[k]; if (tx > 0 && tx < 5 && ty > 0 && ty < 5)c[tx][ty] ^= 1; } dfs(x + 1,ans + 1); c[i][j] ^= 1; for (int k = 0; k < 4; k++){ int tx = i + dx[k],ty = j + dy[k]; if (tx > 0 && tx < 5 && ty > 0 && ty < 5)c[tx][ty] ^= 1; } } signed main() { for (int i = 1; i <= 4; i++) for (int j = 1; j <= 4; j++){ char cc; cin >> cc; if (cc == 'w') c[i][j] = 0; else c[i][j] = 1; } dfs(1,0); if (minn == 9e18) puts("Impossible"); else printf("%lld",minn); return 0; }