首页 > 代码库 > POJ 1681 (开关问题+高斯消元法)
POJ 1681 (开关问题+高斯消元法)
题目链接: http://poj.org/problem?id=1681
题目大意：一堆格子，或白或黄。每次可以把一个改变一个格子颜色，其上下左右四个格子颜色也改变。问最后使格子全部变黄，最少需要改变几个格子。
解题思路：
与POJ 1222类似。
一共只有15*15个格子，设初始解向量黄为0，白为1.
对于每个开关，设其改变状态为x5，上下左右四个开关改变状态分别为x1,x2,x3,x4,
那么有方程x1^x2^x3^x4^x5^初始状态=0。
这样就有15*15个方程。解这15*15个线性方程组，就能得到每个格子的改变状态。
注意这里高斯消元的是一个开关矩阵，而不是黄白矩阵，也就是说，如果最后的解为0，不是表示这个格子为黄，而是这个格子相对于初始状态没有改变。
那么问题就来了，如何知道改变的最少格子？
其实很简单，在得到最终改变格子的状态后，统计一下里面的改变的格子数，也就是解为1的元，就是结果。
同时由于要判断无解情况，所以不能使用POJ 1222中那样的简略写法。
#include "cstdio"#include "iostream"#include "cstring"using namespace std;int ratio[230][230],dir[5][2]={0,0,-1,0,1,0,0,-1,0,1},T,n;void reset(){ for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<5;k++) { int x=i+dir[k][0],y=j+dir[k][1]; if(x>=0&&y>=0&&x<n&&y<n) ratio[i*n+j][x*n+y]=1; }}bool gauss(){ int i,j,k; for(i=0,j=0;i<n*n&&j<n*n;i++,j++) { k=i; for(;k<n*n;k++) if(ratio[k][j]) break; for(int t=j;t<=n*n;t++) if(i!=k) swap(ratio[i][t],ratio[k][t]); if(!ratio[i][j]) {i--;continue;} for(k=i+1;k<n*n;k++) { if(ratio[k][j]) for(int t=j;t<=n*n;t++) ratio[k][t]^=ratio[i][t]; } } k=i; for(i=k; i<n*n; i++) if(ratio[i][n*n]) return false; for(i=k-1; i>=0; i--) { for(j=i+1; j<n*n; j++) ratio[i][n*n]^=(ratio[i][j]&&ratio[j][n*n]); } return true;}int main(){ //freopen("in.txt","r",stdin); char c; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(ratio,0,sizeof(ratio)); reset(); for(int i=0;i<n*n;i++) { scanf(" %c",&c); if(c==‘w‘) ratio[i][n*n]=1; if(c==‘y‘) ratio[i][n*n]=0; } int ans=gauss(); if(!ans) printf("inf\n"); else { int ans=0; for(int i=0;i<n*n;i++) if(ratio[i][n*n]==1) ans++; printf("%d\n",ans); } }}
| 13597338 | neopenx | 1681 | Accepted | 364K | 16MS | C++ | 1651B | 2014-11-04 13:14:49 |
POJ 1681 (开关问题+高斯消元法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。