Задача #M052F

Память 16 MB Время 1000 ms Сложность 47 %

#Перебор

#Depth-First Search

Bayram stoli

Bitvoy do'stlari bilan bayram uyushtirmoqchi. Ammo u do'stlari uchun to'g'ri to'rtburchak shaklidagi stol buyurtma qilmoqchi. U juda sahiy. Shuning uchun iloji boricha ko'proq mehmon o'tirishi mumkin bo'lgan stol buyurtma qilmoqchi. Bunda stol sig'imi uning perimetri bilan bir xil. Bitvoy eng ko'pi bilan necha nafar do'stini taklif qilishi mumkinligi aniqlang. Stolda o'zi ham o'tirishi kerak.

Входные данные:

Kirish faylida birinchi qatorda Bitvoyning uyini o'lchamlari kiritiladi. N, M\((1\le N, M \le 400)\).

Keyingi N qatorda Bitvoy uyining xaritasi M tadan belgi, bunda X -> bu joy allaqachon band, nuqta(.) -> bo'sh joyni anglatadi.

Выходные данные:

Chiqish faylida Bitvoy nechta do'stini chaqirishi mumkin ekanligini chop eting.

Примеры

#	input.txt	output.txt
1	1 1 .	3
2	10 10 ....X..... X......... .......... .......... .......... .......... .......X.. .......... ..X....... ...X......	27

Примечание:

1-testda:

Demak eng ko'pi bilan 2x2 o'lchamli stol buyurtma qilishi mumkin.

P = 2 * (1 + 1) = 4

O'zi ham borligi uchun 4 - 1=3.

2-testda:

Demak eng ko'pi bilan 10x4 o'lchamli stol buyurtma qilishi mumkin.

P = 2 * (4 + 10) = 28

O'zi ham borligi uchun 28 - 1=27.

Telegram Facebook

Отправить решение

Пожалуйста, войдите в систему, чтобы выполнить это действие,если у вас нет учетной записи, вы можете зарегистрироваться в любое время