【BZOJ 4171】 4171: Rhl的游戏 （高斯消元）

时间：2024-07-30 22:34:38

4171: Rhl的游戏

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 74  Solved: 33
[Submit][Status][Discuss]

Description

RHL最近迷上一个小游戏：Flip it。游戏的规则很简单，在一个N*M的格子上，有一些格子是黑色，有一些是白色
。每选择一个格子按一次，格子以及周围边相邻的格子都会翻转颜色（边相邻指至少与该格子有一条公共边的格子
），黑变白，白变黑。RHL希望把所有格子都变成白色的。不幸的是，有一些格子坏掉了，无法被按下。这时，它
可以完成游戏吗？

Input

第一行一个整数T，表示T组数据。
每组数据开始于三个整数n,m,k，分别表示格子的高度和宽度、坏掉格子的个数。接下来的n行，每行一个长度m的
字符串，表示格子状态为'B'或'W'。最后k行，每行两个整数Xi,Yi(1≤Xi≤n,1≤Yi≤m)，表示坏掉的格子。
n,m,k<=256,T<=10

Output

对于每组数据，先输出一行Case #i: (1≤i≤T)
如果可以成功，输出YES，否则输出NO。

Sample Input

2
3 3 0
WBW
BBB
WBW
3 3 2
WBW
BBB
WBW
2 2
3 2

Sample Output

Case #1:
YES
Case #2:
NO

HINT

Source

【分析】

　　今天脑子真的不好，这种题既知道思路也不会打。。还要膜奥爷爷给我理思路了。。

　　首先，显然是高斯消元。但当然不是每个格子都是未知量。其实只要枚举第一行，就能推出全部。

　　$f[i][j]$是bitset表示的点$(i,j)$的状态，他们的异或和表示$(i,j)$这个点按还是不按。

　　第一行$f[1][j]=(0,0,...1,0,0,...)$，只有第$j$位为1。

　　当$(i,j)$初始为$B$，$a[i][j]=1$,否则$a[i][j]=0$。

　　举个栗子：$nw$表示$(2,1)$这个点按还是不按，那么$nw$^$x1$^$x2$=$a[1][1]$ → $nw$=$x1$^$x2$^$a[1][1]$

　　每个点都可以用第一行的$x$和$a$数组表示出来，写成$f[i][j]$即$f[2][1]=(1,1,0,0,0,0,...,a[1][1])$ 【这就是奥爷爷举的例子啦，想了一会我终于懂了

　　【有时候真的不要太纠结这个是个什么方程什么的，就表示你想表示的东西就好了，毕竟异或还是很通用，很多种理解方式都可以使用高斯消元的

　　常数的异或和放在$m+1$位。、

　　对于损坏点$(x,y)$即 $f[x][y][1]$^$f[x][y][2]$^...$f[x][y][m+1]$=0,则$f[x][y][1]$^...$f[x][y][m]$=$f[x][y][m+1] $，看成是$m$个元的方程。

　　对于最后一行，我们前面没有保证他的值是对的，所以要列$m$个方程，

　　$f[n][j]$^$f[n][j-1]$ ^$f[n][j+1]$ ^$f[n-1][j]$=$a[n][j]$ 也把$m+1$项弄到右边去和$a[n][j]$异或得到新的方程。

　　高斯消元判断是否有解就好了。

　　注意每次求$f[i][j]$的时候是保证$(i-1,j)$这个点的状态正确。

　　放弃了抄代码，终于开始自己想，自己打的时候，终于AC了。。

　　事实证明，理解别人的东西还是困难的，还是要自己多多想啊！！

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<bitset>

 using namespace std;

 #define Maxn 310

 char s[Maxn];

 int a[Maxn][Maxn];

 bitset<Maxn > f[Maxn][Maxn],w[*Maxn];

 int n,m,k;

 bool solve()

 {

     for(int j=;j<=m;j++)

     {

        for(int i=;i<=n;i++) f[][j][i]=;

        f[][j][j]=;

     }

     for(int i=;i<=n;i++)

      for(int j=;j<=m;j++)

      {

          f[i][j]=f[i-][j]^f[i-][j];

          if(j>) f[i][j]^=f[i-][j-];

          if(j<m) f[i][j]^=f[i-][j+];

          f[i][j][m+]=f[i][j][m+]^a[i-][j];

      }

     int cnt=;

     for(int i=;i<=k;i++)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         w[++cnt]=f[x][y];

     }

     w[++cnt]=f[n][]^f[n][]^f[n-][];

     w[cnt][m+]=w[cnt][m+]^a[n][];

     for(int j=;j<m;j++) w[++cnt]=f[n][j-]^f[n][j]^f[n][j+]^f[n-][j],w[cnt][m+]=w[cnt][m+]^a[n][j];

     w[++cnt]=f[n][m-]^f[n][m]^f[n-][m];w[cnt][m+]=w[cnt][m+]^a[n][m];

     int i=;

     for(int j=;j<=m;j++)

     {

         int t=;

         for(int k=i;k<=cnt;k++) if(w[k][j]) {t=k;break;}

         if(!t) continue;

         swap(w[i],w[t]);

         for(int k=i+;k<=cnt;k++) if(w[k][j]) w[k]^=w[i];

         i++;

     }

     bool ok=;

     for(int i=;i<=cnt;i++)

     {

         bool p=;

         for(int j=;j<=m;j++) if(w[i][j]!=) {p=;break;}

         if(p&&w[i][m+]) return ;

     }

     return ;

 }

 int main()

 {

     int T,kase=;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d%d",&n,&m,&k);

         for(int i=;i<=n;i++)

         {

             scanf("%s",s+);

             for(int j=;j<=m;j++)

             {

                 if(s[j]=='B') a[i][j]=;

                 else a[i][j]=;

             }

         }

         printf("Case #%d:\n",++kase);

         if(solve()) printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }

2017-04-10 22:15:50

相关文章