12102. Де було печиво?


Відправити розв'язок

Бали: 100
Time limit: 2.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python

Задається сітка з \(H\) рядків і \(W\) стовпців. Нехай \((i,j)\) позначає квадрат у \(i\)-му рядку зверху та \(j\)-му стовпчику зліва.

Спочатку було одне печиво на кожному квадраті всередині прямокутника, висота та ширина якого становила принаймні 2 квадрати, а на інших квадратах не було печива.

Формально існувала рівно одна четвірка цілих чисел \((a,b,c,d)\), яка задовольняла всі наступні умови:

  • \(1≤a<b≤H\)
  • \(1≤c<d≤W\)
  • Було одне печиво на кожному квадраті \((i,j)\), так що \(a≤i≤b,c≤j≤d\), і жодного печива на інших квадратах.

Однак Степан взяв і з'їв одне з печива на сітці. Квадрат, який містив це печиво, тепер порожній.

У якості вхідних даних вам надається стан сітки після того, як Степан з’їв печиво.

Стан квадрата \((i,j)\) задається символом \(S_{i,j}\) ​, де # означає квадрат із печивом, а . означає квадрат без нього.

Знайдіть квадрат, у якому було печиво, яке зʼїв Степан. (Відповідь визначається однозначно.)

Обмеження

  • \(2≤H,W≤500\)
  • \(S_{i,j}\) ​ дорівнює # або .

Формат вхідних даних

Перший рядок містить цілі числа \(H,W\).

Наступні  \(H\) рядків містять по \(W\) символів \(A_{i,j}\).

Формат вихідних даних

У вихідний потік виведіть шукані \(i\) та \(j\) у такому порядку, розділивши їх пробілом.

Приклад вхідних даних

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

Приклад вихідних даних

2 4

Спочатку печиво було на квадратах усередині прямокутника з (2,3) у верхньому лівому куті та (4,5) у нижньому правому куті, і Степан з’їв печиво на (2,4). Таким чином, ви повинні вивести (2,4).

Приклад вхідних даних

3 2
#.
##
##

Приклад вихідних даних

1 2

Приклад вхідних даних

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

Приклад вихідних даних

2 5

Коментарі

Ще немає коментарів.