1248: Злиття островів - ІІ етап, 2017

Перегляд у форматі PDF
Надіслати розв'язок
Бали: 21
Time limit: 1.0s
Memory limit: 64M
Author:
zvit
Problem types

Жителi однiєї невеликої острiвної країни звертаються до юних програмiстiв по допомогу - необхiдно знайти найбiльш економний шлях для об'єднання дрiбних островiв. Всi острови, якi жителi планують з'єднати, розбитi на пари. На планi острови показанi символами " \(X\) " . План має розмiри \(N\) х \(M\) . Два символи " \(X\) " належать одному острову, якщо вони мають спiльну сторону по горизонталi чи вертикалi. Дiагональне сусiдство не є умовою належностi одному острову. Знайдiть мiнiмальну кiлькiсть клiтинок на картi, якi вкажуть оптимальний шлях для злиття островiв.

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

Перший рядок вхiдного потоку мiстить цiлi числа \(N; M\) \(1 ⩽ N; M ⩽ 50\) .

Наступнi \(N\) рядкiв мiстять по \(M\) символiв " \(X\) " або "." - "\(X\)" показує на частину острова, а " . " помiчає на картi воду.

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

Мiнiмальну кiлькiсть символiв " \(X\) " , якi треба добавити на картi мiж островами для їх об'єднання.

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

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

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

3

Пояснення

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....

На мiсце "*" треба поставити символ "X" для оптимального злиття островiв.

Коментарі


  • 0
    Hydra  commented on Лис. 29, 2021, 1:35 після полудня

    Рішення для двох островів спрацювало, тому я так розумію, що так


    • 1
      zvit  commented on Лис. 30, 2021, 11:45 до полудня

      так


  • 0
    Hydra  commented on Лис. 29, 2021, 12:11 після полудня

    "... острови, якi жителi планують з'єднати, розбитi на пари. ..." Це означає, що у вхідних даних буде лиш два острови?