loj 6030「雅禮集訓 2017 Day1」矩陣

NO IMAGE

題目描述

有一個 n×n
n \times nn×n 的矩陣,每個位置 (i,j)
(i, j)(i,j) 如果是 . 表示為白色,如果是 # 表示為黑色。

初始時,每個位置可以是黑色或白色的,(i,j)
(i, j)(i,j) 位置的值會作為 ai,j
a_{i, j}a​i,j​​ 給你。

現在有一種操作,選擇兩個整數 i,j∈[1,n]
i, j \in [1, n]i,j∈[1,n],記 (i,1),(i,2),…,(i,n)
(i, 1), (i, 2), \ldots, (i, n)(i,1),(i,2),…,(i,n) 的顏色為 C1,C2,…Cn
C_1, C_2, \ldots C_nC​1​​,C​2​​,…C​n​​,將 (1,j),(2,j),…,(n,j)
(1, j), (2, j), \ldots, (n, j)(1,j),(2,j),…,(n,j) 的顏色賦為 C1,C2,…,Cn
C_1, C_2, \ldots, C_nC​1​​,C​2​​,…,C​n​​。

你的任務是將整個矩陣變成全黑,如果能夠辦到,輸出最少步數,否則輸出 −1
-1−1。

      

        一道看起來沒有什麼演算法的題,似乎就只能去推結論了。

        最先開始我們可以發現,如果有一個黑點,那麼把它複製到與它相關的每一列,可以構造出來一個全黑行,這個全黑行還可以把每一列去覆蓋,所以如果至少有一個黑點這題就是有解的。

        下面第一步先按列考慮,首先如果一列含有白色格點,那麼這一列肯定需要被塗至少一次,所有設有白色格點的列共為tot列則至少需要被塗tot次。

        第二步再按行考慮,對於每一行來說,這一行是可以給任何一列塗的,由題意可知,那麼如果有一行全黑,那麼它只需要將第一步所考慮的tot列一塗,即可完成了,所以我們下面假設沒有一行是全黑。

       由於用不是全黑的行來專心塗列是沒有意義的,因為還會引進新的白點,所以我們可以列舉將哪一行構造為全黑,然後加上tot即可。

       假設當前在第i行,那麼

       (1)如果第i列至少有一個黑色的,那麼它必定可以轉移到第i行的任意一個位置,所以由於一次只能去覆蓋一列,所以假設本行有x個白色的塊,那麼則需要x次來將它們變成黑色,由於塗的是有白色的列,所以不會將全黑列增添白點,而且由於當前假設的前提是沒有一行是全黑的,我們也不能通過豎著刷將一列變為全黑,所以有白色格點的仍然為tot列。

        (2)如果第i列是一個全白的列,我們並不能通過第i列的任何一個值來將第i行的空缺補成黑色,而又因為至少有一個黑點,所以肯定可以通過一次賦顏色,使第i列有一個黑店,然後與(1)同理,只多了一個步驟,所以如果第i列沒有黑點,則這一行變為全黑的次數為x 1。

       綜上,最終答案就是tot(有白色格點的行數) min(hang[i](第i行白色格點的個數) !hang[i](第i行是否全為白點))

      下附AC程式碼

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 1005
using namespace std;
int n,flag,tot;
char s[maxn][maxn];
int lie[maxn],hang[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i  )
{
scanf("%s",s[i] 1);
int flag1=0;
for(int j=1;j<=n;j  )
{
if(s[i][j]=='#') 
flag=1,hang[i]  ,lie[j]=true;
if(s[i][j]=='.')
flag1=1;
}
tot =flag1;
}
if(!flag){printf("-1\n");return 0;}
int ans=123456789;
for(int i=1;i<=n;i  )
ans=min(ans,tot n-hang[i] !lie[i]);
printf("%d\n",ans);
}