poj2965 The Pilots Brothers' Refrigerator 题解报告

题目传送门

【题目大意】

有一个$4*4$的矩阵,现在要把矩阵内所有的“+”变成“-”,已知如果选取一个位置$(i,j)$改变状态,那么第$i$行和第$j$列的所有位置的状态都会改变,求达到要求的最小步数和改变状态的顺序。

【思路分析】

分析可得,对于某个“+”的位置$(i,j)$,要使它的状态改变而其他位置状态不变,则第$i$行和第$j$列的所有位置(除去$(i,j)$身)都要选出来被改变状态,且当某一个位置的状态被改变偶数次时,相当于没有改变。

【代码实现】

poj2965 The Pilots Brothers' Refrigerator 题解报告
 1 #include<iostream>
 2 #include<cstdio>
 3 #define rg register
 4 #define go(i,a,b) for(rg int i=a;i<=b;i++)
 5 using namespace std;
 6 int ans,x[20],y[20];
 7 bool mark[5][5];
 8 char c[5][5];
 9 int main(){
10     go(i,1,4){
11         scanf("%s",c[i]+1);
12         go(j,1,4){
13             if(c[i][j]=='+'){
14                 mark[i][j]=!mark[i][j];
15                 go(k,1,4){
16                     mark[i][k]=!mark[i][k];mark[k][j]=!mark[k][j];
17                 }
18             }
19         }
20     }
21     go(i,1,4) go(j,1,4)
22         if(mark[i][j]) x[++ans]=i,y[ans]=j;
23     printf("%d\n",ans);
24     go(i,1,ans)
25         printf("%d %d\n",x[i],y[i]);
26     return 0;
27 }
代码戳这里
上一篇:2019牛客暑期多校训练营(第九场)All men are brothers——并查集&&组合数


下一篇:第二章:常用UI组件