12080. Хрестики


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

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

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

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

Кожна клітинка сітки містить символ # або . . Нехай \(C[i][j]\) — символ, написаний на \((i,j)\). Для цілих чисел \(i\) та \(j\) таких, що принаймні одне з \(1≤i≤H\) та \(1≤j≤W\) порушується, ми визначаємо \(C[i][j]\) як ..

\((4n+1)\) квадрати, що складаються з \((a,b )\) і \((a+d,b+d)\),\((a+d,b−d)\),\((a−d,b+d)\),\((a−d,b−d)\) \((1≤d≤n,1≤n)\), називаються хрестиком розміру \(n\) з центром \((a,b)\) тоді і тільки тоді, коли задовольняються всі наступні умови:

  • \(C[a][b]\) дорівнює #.
  • \(C[a+d][b+d]\),\(C[a+d][b−d]\),\(C[a−d][b+d]\) і \(C[a−d][b−d]\) є #, для всіх цілих \(d\) таких, що \(1≤d≤n\),
  • принаймні один із \(C[a+n+1][b+n+1]\),\(C[a+n+1][b−n−1]\),\(C[a−n−1][b+n+1]\) та \(C[a −n−1][b−n−1]\) дорівнює ..

Наприклад, сітка на наступному малюнку має хрестик розміру 1 з центром (2,2) та інший хрестик розміру 2 з центром (3,7).

На сітці кілька хрестиків. У клітинках не пишеться #, за винятком тих, які містять хрестик. Крім того, жодні два квадрати, які складаються з двох різних хрестів, не мають спільного кута.

Дві сітки на наступному малюнку є прикладами сіток, де два квадрати, що містять різні хрести, мають спільний кут; такі сітки не надаються як вхідні дані. Наприклад, ліва сітка недійсна, оскільки (3,3) і (4,4) мають спільний кут.

Нехай \(N=min(H,W)\), а \(S_n\) — кількість хрестиків розміру \(n\). Знайдіть \(S_1 ​ , S_2 ​ ,…, S_N ​\) .

Обмеження

  • \(3≤H,W≤100\)
  • \(C[i][j]\) дорівнює # або . .
  • Немає двох різних квадратів, які складаються з двох різних хрестів, спільного кута.
  • \(H\) і \(W\) — цілі числа.

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

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

Наступні  \(N\) рядків містять \(C[i][j]\).

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

У вихідний потік виведіть \(S_1 ​ , S_2 ​ ,… S_N ​\) , розділивши їх пробілами.

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

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

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

1 1 0 0 0

Як описано в умові задачі, є хрестик розміру 1 з центром (2,2) і інший розміром 2з центром (3,7).

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

3 3
...
...
...

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

0 0 0

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

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

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

3 0 0

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

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

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

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Коментарі

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