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

Перегляд у форматі PDF
Надіслати розв'язок
Бали: 21,00 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
zvit
Problem types
Allowed languages
Assembly, Awk, Brain****, C, C++, Java, mono C#, Pascal, Perl, Python, Sed, Text, vb

Жител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в.

Коментарі

Please read the guidelines before commenting.


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

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


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

      так


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

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