题目大意
《飞行员兄弟:跟随条纹象》游戏中有一个任务,玩家需要打开一个冰箱。
冰箱门上有16个把手。每个把手都可以处于两种状态之一:打开或关闭。只有当所有把手都打开时,冰箱才是打开的。手柄用矩阵4х4表示。你可以在任何位置(i,j)改变一个把手的状态(1≤i, j≤4)。然而,这也会同时改变第i行和第j列的所有手柄的状态。
你的任务是找到打开冰箱所需的最小把手切换次数。
思路
与poj1753类似,每个格子只有0或1两种状态,那么只有奇数次的操作是有效地。结合题目4×4的小规模,考虑直接枚举答案。
接下来就是思考枚举方式。因为我们知道偶数次的操作等于没有操作,那么我们可以等效处理:在对(i,j)进行切换操作时,同时对同行列的把手也进行一次操作,那么整个过程等效为仅对(i,j)进行了一次有效操作。
参照上图,黄色区域的方格被操作了两次,等效为0次;红色区域的方格被操作了四次,等效为0次;黑色方格被操作了七次,等效为1次。
那么我们就得到了一个策略:在对某个方格(i,j)进行切换时,同时对同行列的方格也进行切换就能确保只改变(i,j)的状态。
那么我们只需要对所有”+”执行上述策略,并记录相关方格被操作的次数,最后在统计被操作数是奇数的方格就能得到所有有效操作。
代码
#include <cstdio> #include <iostream> using namespace std; int ans = 0; int cnt[5][5]; bool mp[5][5]; void switchOn(int x, int y) { for(int i = 0; i < 4; i++) { mp[x][i] = !mp[x][i]; if(i == x) continue; mp[i][y] = !mp[i][y]; } cnt[x][y]++; } int main() { char tmp; for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) { cin >> tmp; mp[i][j] = (tmp == '-'); } for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) if(mp[i][j] == 0) for(int k = 0; k < 4; k++) { switchOn(i, k); if(k == i) continue; switchOn(k, j); } for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) if(cnt[i][j] % 2) ans++; cout << ans << endl; for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) if(cnt[i][j] % 2) cout << i + 1 << " " << j + 1 << endl; return 0; }
评论
还没有任何评论,你来说两句吧!