Будівництво басейну#4013
Ви працюєте в міжнародній компанії з будівництва басейнів, яка спеціалізується на створенні плавальних зон. Новий клієнт бажає побудувати кілька нових зон басейнів.
Зона басейну являє собою прямокутну сітку розміром w \times h квадратних ділянок, що можуть містити нуль або більше (можливо, роз'єднаних) басейнів. Басейн складається з однієї або кількох з'єднаних ділянок з ямами, які згодом будуть заповнені водою. Спочатку ви маєте ділянку землі, де кожна ділянка є або ямою ('.'), або рівною травою ('#'). Щоб перетворити цю землю на зону басейну, ви повинні дотримуватися наступних правил:
Ви можете залишити ділянку без змін. Це безкоштовно.
Якщо ділянка спочатку є травою, ви можете викопати там яму. Це коштує євро.
Якщо ділянка спочатку є ямою, ви можете заповнити її і покласти траву зверху. Це коштує євро.
Ви повинні встановити спеціальні елементи межі вздовж кожного краю, що розділяє остаточну ділянку з травою і остаточну ділянку з ямою, щоб запобігти витіканню води з басейну. Це коштує євро за кожен елемент межі.
Найзовнішні рядки та стовпці зони басейну завжди повинні бути травою.
Ваше завдання — обчислити вартість найдешевшої можливої зони басейну, враховуючи планування існуючої ділянки землі.
На першому рядку задано позитивне ціле число: кількість тестових випадків, не більше . Далі для кожного тестового випадку:
один рядок з двома цілими числами і (2 \leq w, h \leq 50): ширина і висота будівельного майданчика.
один рядок з трьома цілими числами , і (1 \leq d, f, b \leq 10000): вартість викопування нової ями, заповнення існуючої ями та встановлення елемента межі між басейном і ділянкою з травою.
рядків по символів кожен, що представляють планування оригінального будівельного майданчика.
Для кожного тестового випадку виведіть:
один рядок з цілим числом: вартість будівництва найдешевшої можливої зони басейну з оригінальної ділянки землі.
Приклад 1