← 返回题目列表

AtCoder · abc305_c

E. 偷袭饼干拾取器

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

分数: 300 点

问题陈述

有一个网格 H 行和 W 列。让 (i, j) 表示 i从顶部开始的第行和 j左起第 列。
最初,矩形内的每个正方形上都有一个 cookie,其 高度和宽度至少为 2 正方形长,并且其他方块上没有 cookie。
形式上,只有一个整数的四元组 (a,b,c,d) 满足以下所有条件。

  • 1 \leq a \lt b \leq H
  • 1 \leq c \lt d \leq W
  • 每个方格上有一个饼干 (i, j) 这样 a \leq i \leq b, c \leq j \leq d,并且其他方块上没有 cookie。

然而,Snuke 拿走了并吃掉了网格上的一块饼干。
包含该 cookie 的方块现在是空的。

作为输入,您将获得 Snuke 吃掉 cookie 后网格的状态。
方块的状态 (i, j) 作为字符给出 S_{i,j},其中 # 表示带有饼干的正方形,并且 . 表示没有正方形的正方形。
找到包含被 Snuke 吃掉的饼干的方块。 (答案是唯一确定的。)

约束

  • 2 \leq H, W \leq 500
  • S_{i,j} is # or ..

输入

输入由标准输入按以下格式给出:

H W
S_{1,1}S_{1,2}\dotsS_{1,W}
S_{2,1}S_{2,2}\dotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\dotsS_{H,W}

输出

让 (i, j) 方块里有 Snuke 吃掉的饼干。打印 i 和 j 按此顺序,用空格分隔。


示例输入 1

5 6
......
..#.#.
..###.
..###.
......

示例输出 1

2 4

最初,饼干位于矩形内的正方形上, (2, 3) 作为左上角, (4, 5) 作为右下角,Snuke 吃了饼干 (2, 4)。因此,您应该打印 (2, 4).


示例输入 2

3 2
#.
##
##

示例输出 2

1 2

最初,饼干被放置在矩形内的正方形上, (1, 1) 作为左上角, (3, 2) 作为右下角,Snuke 吃了饼干 (1, 2).


示例输入 3

6 6
..####
..##.#
..####
..####
..####
......

示例输出 3

2 5