AKAeclipse抓羊记
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
一切起源于AKAeclipse某天刷到了一个小视频……
（注：该图片实际上没有“正解”，“歪解”是用火把赶走狼。）
题目描述
给你一个n行m列的字符矩阵代表羊圈，每个位置只可能是' * '和' # '二者其中之一。 ' * '表示该位置是空位置，可以容纳小羊；' # '则表示该位置被堵死，不可容纳小羊。
每只小羊会占用相邻的两个格子。AKAeclipse想让你帮忙算一下：在最优策略下，羊圈中最多能容纳多少只小羊呢？（不考虑如何把羊赶进羊圈。）
输入格式
第一行输入两个正整数n、m（1≤n、m≤50），表示接下来要输入的字符矩阵是n行m列的。
此后n行，每行输入一个长度为m字符串，字符串仅由' * '和' # '组成。
输出格式
对于每组数据，输出一个正整数x，表示最多能容纳的小羊个数。
样例
1 8
#*******
3
4 7
*###*##
******#
####*##
#######
3
限制与提示
样例里的情况如图所示。方案不唯一，但可以发现没有更好的答案了。
2026 XAUT 西安理工大学新生赛-同步赛 & XJSACM Round 1
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 15
- 开始于
- 2026-1-11 13:00
- 结束于
- 2026-1-11 18:00
- 持续时间
- 5 小时
- 主持人
-
xhhyj
- 参赛人数
- 6