怎么几乎和关灯那题一样啊!那肯定是差不多的做法咯!
先钦定第一行的操作,然后还没有被关上你给定就让下面的把它关上..等等,下面2,3,4行好像都可以把它关上欸
..那咋办..
在看看数据范围,是4*4的矩形..
那么..$O(2^{n^2})$的枚举所有情况,暴力$O(n^2)$check就过了…
总时间复杂度$O(n^2\times 2^{n^2}),n=4$足以应对
代码里枚举的s,就代表操作位置的二进制压缩.$(i,j)$对应着$s$的第$(i-1)*4+j-1$位
//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
typedef unsigned un;
typedef long long ll;
typedef std::pair<ll,ll> pll;
const ll INF=1ll<<58;
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
bool umin(ll &a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
bool umax(ll &a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
ll abs(ll x)
{
return x>0?x:-x;
}
/**********/
bool a[5][5],tmp[5][5],way[5][5];
ll ans=ll(1e9);
bool check(ll s)
{
memcpy(tmp,a,sizeof a);
for(ll i=1;i<5;++i)
for(ll j=1;j<5;++j)
if(s&(1<<((i-1)*4+j-1)))
{
tmp[i][j]=!tmp[i][j];
for(ll x=1;x<5;++x)tmp[x][j]=!tmp[x][j];
for(ll y=1;y<5;++y)tmp[i][y]=!tmp[i][y];
}
for(ll i=1;i<5;++i)
for(ll j=1;j<5;++j)
if(tmp[i][j])return 0;
return 1;
}
ll calc(ll n)
{
ll res=0;
while(n)
{
res+=(n&1);
n>>=1;
}
return res;
}
void work()
{
for(ll s=0;s<(1<<16);++s)
{
ll cost=calc(s);
if(cost<ans&&check(s))
{
ans=cost;
for(ll i=1;i<5;++i)
for(ll j=1;j<5;++j)
if(s&(1<<((i-1)*4+j-1)))way[i][j]=1;
else way[i][j]=0;
}
}
}
int main()
{
for(ll i=1;i<5;++i)
for(ll j=1;j<5;++j)
{
char c=getchar();
if(c!='-'&&c!='+')c=getchar();
if(c=='-')a[i][j]=0;
else a[i][j]=1;
}
work();
printf("%lld\n",ans);
for(ll i=1;i<5;++i)
for(ll j=1;j<5;++j)
if(way[i][j])
printf("%lld %lld\n",i,j);
return 0;
}