膜法记录

[编程题]膜法记录

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛最近在玩一款叫做《膜法记录》的游戏，这个游戏的机制是这样的：

在一局游戏中，所有的敌人都排布在一个 ${n}$ 行 ${m}$ 列的网格中，牛牛指挥着他的魔法少女对敌人进行攻击。

攻击有两种类型：行blast，列blast

行blast能消灭一整行的敌人，列blast能消灭一整列的敌人

牛牛总共能够释放 ${a}$ 次行blast， ${b}$ 次列blast

给定某局游戏的初始局面，请问牛牛能否将敌人全歼？

输入描述:

第一行包含一个正整数，表示测试数据组数，接下来是组测试数据
每组测试数据的第一行有四个正整数 ,,,
接下来有行，每行是一个长度为的字符串，第行第列的字符如果是*则说明这里有一个敌人，如果是.说明这里没有

输出描述:

对每组测试数据输出一行，如果能消灭所有的敌人，就输出yes，否则输出no

示例1

输入

2
3 3 1 2
..*
.*.
*..
4 4 3 1
..**
**..
.**.
*.**

输出

yes
no

说明

第一个样例，我可以在第一行放一个行blast，然后前两列都放一个列blast，就把敌人给全歼了。第二个样例，我不管怎么安排攻击策略，都没法全歼敌人

备注:

要么

要么

对于以上两种情况都满足：

算法知识视频讲解

健康快乐最重要

发表于 2020-03-24 09:10:13

段大佬写的二进制压缩小白看不太懂。所以参考其他大佬的思路，用dfs暴力搜索写了一个。思路：一开始所有的行都不标记，然后再回溯的时候依次遍历所有的情况(依次标记所有的组合)，当所有的行blast都用完时并且列blast小于要消除的列时，说明可以消除完，返回true。其他情况下都为false。 #inc 展开全文

苟且的狮子

发表于 2020-07-21 00:07:16

枚举优化题意：牛牛最近在玩一款叫做《膜法记录》的游戏，这个游戏的机制是这样的：在一局游戏中，所有的敌人都排布在一个 {n}n 行 {m}m 列的网格中，牛牛指挥着他的魔法少女对敌人进行攻击。攻击有两种类型：行blast，列blast行blast能消灭一整行的敌人，列blast能消灭一整列的敌人牛展开全文

白菜茄子

发表于 2020-03-25 22:52:19

网址：https://ac.nowcoder.com/acm/contest/4784/A 题目描述牛牛最近在玩一款叫做《膜法记录》的游戏，这个游戏的机制是这样的：在一局游戏中，所有的敌人都排布在一个 {n}n 行 {m}m 列的网格中，牛牛指挥着他的魔法少女对敌人进行攻击。攻击有两种类型：行bl 展开全文