Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
123898 | 黄一航 | 翻转棋盘 | C++ | 通过 | 100 | 1 MS | 252 KB | 1060 | 2024-01-23 10:07:21 |
#include <bits/stdc++.h> #define int long long using namespace std; int c[5][5]; int minn = 9e18; int dx[] = {0,1,0,-1}; int 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; int j = (x % 4)?(x % 4):4; c[i][j] ^= 1; for (int k = 0; k < 4; k++) { int tx = i + dx[k]; int 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]; int 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\n",minn); return 0; }