AT_abc305_c [ABC305C] Snuke the Cookie Picker

题目描述

有一个高为 $H$，宽为 $W$ 的网格。自上而下的第 $i$ 行，自左而右的第 $j$ 列的格子记作 $(i, j)$。

一开始，在网格上某个纵向和横向都不少于 $2$ 格的部分矩形的内部的每个格子上都放有一块饼干，其余格子上没有饼干。

形式化地说，存在且仅存在一组满足以下所有条件的四元组整数 $(a, b, c, d)$：

• $1 \leq a < b \leq H$
• $1 \leq c < d \leq W$
• 对于所有满足 $a \leq i \leq b,\ c \leq j \leq d$ 的格子 $(i, j)$，都放有一块饼干，其余格子上没有饼干。

然而，すぬけ君吃掉了网格上的某一块饼干。被吃掉的格子变成没有饼干的状态。

现在给出すぬけ君吃掉饼干后的网格状态。每个格子的状态用字符 $S_{i,j}$ 表示，# 表示该格子上有饼干，. 表示该格子上没有饼干。

请你输出すぬけ君吃掉的那块饼干原本所在的格子的位置。保证答案唯一。

输入格式

输入按以下格式从标准输入给出。

$H$ $W$
$S_{1,1} S_{1,2} \dots S_{1,W}$
$S_{2,1} S_{2,2} \dots S_{2,W}$
$\vdots$
$S_{H,1} S_{H,2} \dots S_{H,W}$

输出格式

设すぬけ君吃掉的饼干原本所在的格子为 $(i, j)$。请按顺序输出 $i$ 和 $j$，用空格隔开。

输入输出样例 #1

输入 #1

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

输出 #1

2 4

输入输出样例 #2

输入 #2

3 2
#.
##
##

输出 #2

1 2

输入输出样例 #3

输入 #3

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

输出 #3

2 5

说明/提示

限制条件

• $2 \leq H, W \leq 500$
• $S_{i,j}$ 仅为 # 或 .

样例解释 1

一开始，饼干放在以 $(2, 3)$ 为左上角、$(4, 5)$ 为右下角的部分矩形内部，すぬけ君吃掉了 $(2, 4)$ 上的饼干。因此输出 $2\ 4$。

样例解释 2

一开始，饼干放在以 $(1, 1)$ 为左上角、$(3, 2)$ 为右下角的部分矩形内部，すぬけ君吃掉了 $(1, 2)$ 上的饼干。因此输出 $1\ 2$。

由 ChatGPT 4.1 翻译