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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!