← 返回题目列表

Codeforces · 965/B

B. 战舰

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

阿尔卡迪正在玩战舰。这个游戏的规则其实并不重要。

有一个包含 $$$n \times n$$$ 个单元格的字段。场上应该正好有一个 $$$k$$$-decker,即。 e.一艘水平或垂直方向有 $$$k$$$ 个单元格的船。然而,阿尔卡迪并不知道它位于何处。对于每个单元格,阿尔卡迪都知道它是否绝对是空的或者可以包含船的一部分。

考虑船舶的所有可能位置。找到属于船舶最大可能数量的不同位置的单元格。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 100$$$) — 字段的大小和船舶的大小。

接下来的 $$$n$$$ 行包含该字段。每行包含 $$$n$$$ 字符,每个字符要么是“#”(表示绝对为空的单元格)要么是“.” (表示可以属于该船的单元格)。

输出

输出两个整数 - 属于船舶不同位置的最大可能数量的单元格的行和列。

如果有多个答案,则输出其中任何一个。特别是,如果场上无法放置船只,则可以输出任何单元格。

示例

输入 #1

4 3
#..#
#.#.
....
.###

输出 #1

3 2

输入 #2

10 4
#....##...
.#...#....
..#..#..#.
...#.#....
.#..##.#..
.....#...#
...#.##...
.#...#.#..
.....#..#.
...#.#...#

输出 #2

6 1

输入 #3

19 6
##..............###
#......#####.....##
.....#########.....
....###########....
...#############...
..###############..
.#################.
.#################.
.#################.
.#################.
#####....##....####
####............###
####............###
#####...####...####
.#####..####..#####
...###........###..
....###########....
.........##........
#.................#

输出 #3

1 8

注意

下图显示了第一个样本中包含单元格 $$$(3, 2)$$$ 的船舶的三个可能位置。