← 返回题目列表

Codeforces · 648/A

A. 最高涨幅

中文机器翻译题面 查看原题

山脉的轮廓以“.”的矩形表格的形式示意性地指定。 (空白区域)和“*”(山的一部分)。每个表列至少包含一个星号。保证任何“*”字符要么位于矩阵的底行,要么在其正下方有另一个“*”字符。

........................*..*.......*.**.......*.**..*...**.************ 山脉的示例图像。

旅游路线从左到右穿过整个山脉。每天,游客都会向右移动 - 到图中相邻的列。当然,每次他上升(或下降)到山的最高点时,都会在相应的列中。

假设游客最初位于第一列的最高点,并将在最后一列的最高点结束他的路线,找到两个值:

- 每日最大上升(如果山脉轮廓没有上升,则等于 0),
- 当天的最大下降(如果山脉轮廓中没有下降,则等于 0)。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100) — 分别是原理图图像中的行数和列数。

接下来是 n 行,每行 m 个字符 - 山脉的示意图。示意图中的每个符号都是“.”。或者 ”*”。矩阵的每一列至少包含一个“*”字符。保证任何“*”字符要么位于矩阵的底行,要么在其正下方有另一个“*”字符。

输出

打印两个空格分隔的整数:

- 每日最大上升值(如果山脉轮廓没有上升,则为 0),
- 当天最大下降值(如果山脉剖面中没有下降,则为 0)。

示例

输入 #1

6 11
...........
.........*.
.*.......*.
**.......*.
**..*...**.
***********

输出 #1

3 4

输入 #2

5 5
....*
...**
..***
.****
*****

输出 #2

1 0

输入 #3

8 7
.......
.*.....
.*.....
.**....
.**.*..
.****.*
.******
*******

输出 #3

6 2

注意

在第一个测试示例中,山的高度为:3, 4, 1, 1, 2, 1, 1, 1, 2, 5, 1。最高海拔为 3,位于 9 号山(其高度为 2)和 10 号山(其高度为 5)之间。最大下降为 4,位于 10 号山(其高度为 5)和 11 号山(其高度为 1)之间。

在第二个测试示例中,山的高度为:1、2、3、4、5。最大的上升等于 1,例如位于 2 号山(其高度为 2)和 3 号山(其高度为 3)之间。由于该山脉没有下降,因此最大下降值为 0。

在第三个测试示例中,山的高度为:1, 7, 5, 3, 4, 2, 3。最高海拔为 6,位于 1 号山(其高度为 1)和 2 号山(其高度为 7)之间。最大下降等于 2,位于 2 号山(其高度为 7)和 3 号山(其高度为 5)之间。同样的下降位于 5 号山(其高度为 4)和 6 号山(其高度为 2)之间。