xtu oj 1271 color

2023-12-14 17:58:44

题目描述

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;

文章来源:https://blog.csdn.net/m0_75005390/article/details/134916396
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。