消灭星星

NC219037. 消灭星星

描述

给出一个 ${N*N}$ 的矩阵，里面有M种字母和若干个星号 ${*}$ 组成，每种字母不止一个。你每次可以消除矩阵的一行或者一列，是否存在至少 ${M-K}$ 种字母完全不受影响的情况下消除掉所有的星星？

输入描述

第一行给出一个正整数 ${T}$ ，表示 ${T}$ 组输入

每组输入先给出三个正整数 ${N，M，K}$

接下来给出一个 ${N*N}$ 的字符矩阵

输入保证给出的字母是前 ${M}$ 个大写字母

$1 \le T \le 100,1 \le N \le 20,0 \le M \le 10,0 \le K \le M$

输出描述

对应每组输入在一行中输出 "yes" or "no"

示例1

输入:

3
5 2 1
....*
*AA..
*A**.
..*.B
..*BB
5 2 1
....*
*AA..
*A**.
..**B
..*BB
5 2 1
....*
*AA..
*A.*.
..**B
..*BB

输出:

yes
no
yes

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 396K, 提交时间: 2021-03-21 09:47:16

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int i,j,k,s,n,m,t,T;
	char R[25][25];
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&t);
		for(i=0;i<n;i++)scanf("%s",R[i]);
		for(i=0;i<(1<<m);i++)
		{
			bool V[15]={0},H[25]={0},L[25]={0},flag=1;
			for(s=j=0;j<m;j++)if((1<<j)&i)V[j]=1,s++;
			if(s!=m-t)continue;
			for(j=0;j<n;j++)
				for(k=0;k<n;k++)if(R[j][k]>='A'&&R[j][k]<='Z'&&V[R[j][k]-'A'])H[j]=L[k]=1;
			for(j=0;flag&&j<n;j++)
				for(k=0;flag&&k<n;k++)if(R[j][k]=='*'&&H[j]&&L[k])flag=0;
			if(flag)break;
		}
		if(i<(1<<m))printf("yes\n");
		else printf("no\n");
	}
	return 0;
}