题解 | #B 牛客推荐系统开发之女装药水#

B题的奇解？

循环最多三次，每次找图中是1的点，碰到就在这地方扔药水。
时间复杂度O（1）？甚至可以解1000*1000的矩阵？

比赛时我写的循环是跑80000次
原理推测：既然要把所有点都变成0，那就碰到一个1就变一个，因为可能会影响之前的，所以再遍历。至于遍历3次即可应该是和只有0,1两个结果有关。遍历超过3次那么结果就会和之前的某次重复

```
#include <bits stdc++.h>
const int maxn=8;
const int n=4;
using namespace std;

int ach[8]={0,0,1,0,-1};
int bch[8]={0,1,0,-1,0};

bool gra[maxn][maxn];
bool flag=1;

int main(){

int i,j;
int x;

memset(gra,0,sizeof(gra));

string s;

for(i=1;i<=n;i++)
{
    cin>>s;
    for(j=1;j<=n;j++)
    {
        if(s[j-1]=='1')
        {
            gra[i][j]=1;
        }
    }

}


// 1->0
int time=3;

while(time--)
{
for(i=1;i<=n;i++)
{
    for(j=1;j<=n;j++)
    {
        if(gra[i][j])
        {
            for(int k=0;k<=4;k++)
            {
                gra[i+ach[k]][j+bch[k]]=!gra[i+ach[k]][j+bch[k]];
            }
        }

    }

}

flag=1;

for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        if(gra[i][j])
        {
            flag=0;
            break;
        }
    }       
    if(flag==1)
        break;
}




if(flag)
    printf("YES\n");
else
    printf("NO\n");

}
```