首先不难想到一个贪心，就是先填出一个全黑的行，然后再用其填黑列。
而且在其中“填出一个全黑的行步数”我们应该最小化。
这个贪心的正确性证明如下：
必要性：填黑列的必要条件为有一个全黑的行。
充分性：“填黑列的步数”就是“非全黑列的数量”。
显然，如果填出一个全黑的行的过程中有列变成了全黑，那么这个行也是全黑，这与全黑行不存在矛盾。
进一步地，无论如何去生成一个全黑的行，“全黑列的数量”始终不改变，因此“填黑列的步数”不改变。
因此最小化答案就是最小化“填出一个全黑的行步数”。
综上所述，我们的贪心策略是最优的。
我们也可以扩展结论：
无解的情况当且仅当不存在黑点。
否则，这个黑点一定可以填出一个全黑行，策略是先覆盖其他所有列，再覆盖自身。
那么如何最小化“填出一个全黑的行步数”呢？我们发现关键所在是白点，我们可以进行操作填黑它。
我们设对应的操作为
(
x
,
y
)
(x,y)
(x,y),白点为
(
a
,
y
)
(a,y)
(a,y),则
(
x
,
a
)
(x,a)
(x,a) 为黑。
-
若存在
(
x
,
a
)
(x,a)
(x,a) 为黑，则只需要一步。
-
否则，我们先进行一个操作染黑
(
x
,
a
)
(x,a)
(x,a)，设操作为
(
b
,
a
)
(b,a)
(b,a),则黑点为
(
b
,
x
)
(b,x)
(b,x)，此时，
(
b
,
x
)
(b,x)
(b,x)已经可以是任意黑点，而且我们只需要操作一次就可以染黑需要的
(
x
,
a
)
(x,a)
(x,a)，所以是最优的。
到此，贪心就没有问题了。
#include
#define LL long long
using namespace std;
const LL N=3005;
const LL inf=1e18;
LL n,a[N],b[N],cnt,mn=inf,hav[N],sum;
char c[N];
int main()
{
cin>>n;
for(int i=1;in;i++)
{
scanf("%s",c+1);//数据有误，请务必这样读入
for(int j=1;jn;j++)
{
if(c[j]=='#')a[i]++,b[j]++,sum++;
}
}
if(sum==0)
{
puts("-1");
return 0;
}
for(int i=1;in;i++)
{
mn=min(mn,n-a[i]+(b[i]==0));
}
for(int i=1;in;i++)
{
if(b[i]!=n)cnt++;
}
coutmn+cntendl;
return 0;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
