a
2023-08-06 09:24:03
发布于：广东
2阅读
0回复
0点赞
T4006.尼斯湖水怪的搜寻
通过率：56.45%
加入题单
题目描述
Background
尼斯湖水怪是地球上最神秘也是最吸引人的未知生物之一。早在1500多年前，英国就开始流传尼斯湖中藏有巨大怪物时常出来吞食人畜的故事。古代一些人甚至宣称曾经目击过这种怪兽，有人说它长着大象的长鼻，浑身柔软光滑；有人说它是长颈圆头；有人说它出现时泡沫层层，四处飞溅；还有人说它口吐烟雾，使湖面有时雾气腾腾等各种传说颇不一致，通过新闻与影视形象传播，一传十，十传百，越传越广，越说越神秘，听起来令人生畏，可这毕竟是一个奇异传闻。
为了查明水怪的真身，在1987年，当地组织了一次大规模水怪搜索，耗资100万英镑，通过声呐来探测湖中的生物。
Description
现在前往
�
×
�
n×m的尼斯湖泊，求投下最少的声呐便可以搜索到尼斯湖水怪。
这种声呐的搜索范围是相邻四周。
湖泊四周是没有必要搜索的，因为水怪身体很大，狭小的四周一圈容纳不下。
下图
�
x为声呐位置，阴影部分是声呐可以搜索的范围，以及
9
×
13
9×13的尼斯湖所需要的最少声呐数其中一种放置方法。
尼斯湖水怪
Format
Input
一行两个正整数
�
,
�
n,m表示尼斯湖泊。
Output
输出一个整数表示最少所需声呐数量。
Samples
输入样例1：
6 6
输出样例1：
4
输入样例2：
9 13
输出样例2：
12
输入样例3：
7 7
输出样例3：
4
Limitation
1s, 128MiB for each test case.
有帮助，赞一个