題目描述

Alice在玩一個游戲，她在一個m×n的格子里，隨機涂黑k個格子。然后她每次可以把一行或者一列的格子染成紅色，但是這一行中不能有黑色的格子。 請問她最多能把多少個格子涂成紅色？

輸入

第一行是一個整數T(T≤100)，表示樣例的個數。 每個樣例的第一行是m(1≤m≤100),n(1≤n≤100),k(0≤k≤m×n)。 以后的k行,每行兩個整數x(1≤x≤m),y(1≤y≤n)，表示(x,y)為黑色格子。

輸出

每行輸出一個樣例的結果。

樣例輸入

1
3 4 2
1 1
3 3

樣例輸出

8

AC代碼

#include<stdio.h>
int main(){int T;scanf("%d",&T);while(T--){int a[105][105]={};//為0表示未染色 int m,n,K;scanf("%d%d%d",&m,&n,&K);int i,j,k;for(i=0;i<K;i++){int x,y;scanf("%d%d",&x,&y);a[x][y]=1;//黑色的標記為1 }//遍歷行 for(i=1;i<=m;i++){int flag=1;for(j=1;j<=n;j++){if(a[i][j]==1){flag=0;break;}}if(flag){for(k=1;k<=n;k++){a[i][k]=-1;//染色標記為-1 }}} //遍歷列 for(j=1;j<=n;j++){int flag=1;for(i=1;i<=m;i++){if(a[i][j]==1){flag=0;break;}}if(flag){for(k=1;k<=m;k++){a[k][j]=-1;//染色標記為-1 }}} int cnt=0;for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(a[i][j]==-1)cnt++;}}printf("%d\n",cnt);
}
} 

解題思路：首先將黑色格子標記為1，這里二維數組行和列都是從1開始的。用標記法解決重復染色問題！！！這里可以遍歷行和列，染色的標記為-1，最后遍歷整個數組，如果a[i][j]=-1,則染色塊+1；