Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
F. Паша ба Хоолой
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Нэгэн $A$ намын уулзалтан дээр сайд Пэйвэл хотын ус зайлуулах сувгийн системийг сайжруулан шинэ хоолой барихыг санаачилжээ.
Хот нь $n × m$ тэгш өнцөгт хэлбэртэй талбайтай. Энэ талбай нь нэгж квадратуудад хуваагдсан. Квадрат болгон нь хоосон (хоолой энэ дээр баригдах боломжтой) эсвэл дүүрэн (хоолой энэ дээр баригдах боломжгүй) байна. Хоосон квадрат болгон '$.$' тэмдэгтээр тэмдэглэгдэнэ. Аарин дүүрэн квадрат болгон нь '$#$' тэмдэгтээр тэмдэглэгдэнэ.
Хоолой нь дараах шаардлагуудыг хангах ёстой:
- Хоолой нь $1$ өргөнтэй олон шулуунуудын нийлбэр байх ёстой,
- Хоолой хоосон квадрат дээр л баригдах ёстой,
- Хоолой нь талбайн ирмэгээс эхлэх ёстой, гэхдээ булангаас эхэлж болохгүй,
- Хоолой нь талбайн ирмэг дээр дуусах ёстой, гэхдээ буланд дуусч болохгүй,
- Хоолой нь хамгийн ихдээ 2 удаа л эргэх боломжтой ($90$ градусаар),
- Хоолой нь хүрээний квадратуудад зөвхөн 2-хон удаа орох боломжтой (хүрээний гэдэг нь хамгийн захын квадратуудыг хэлж байгаа болно),
- Хэрвээ хоолой нь ганцхан шулуунаас бүтэж байвал түүний эцсийн байрлалын ирмэг нь эхлэлийн байрлалын ирмэгээс ялгаатай байх ёстой,
- Хоолойны хүрээний бус квадрат болгонд яг 2 ширхэг хоолой агуулж буй хөрш квадрат байх ёстой,
- Хоолойны хүрээний квадрат болгонд яг 1 ширхэг хоолой агуулж буй хөрш квадрат байх ёстой.
Энд хэдэн зөвшөөрөгдсөн хоолойны зураглал байна:
....# ....# .*..#
***** ****. .***.
..#.. ..#*. ..#*.
#...# #..*# #..*#
..... ...*. ...*.
Энд хэдэн зөвшөөрөгдөөгүй хоолойны зураглал байна:
.**.# *...# .*.*#
..... ****. .*.*.
..#.. ..#*. .*#*.
#...# #..*# #*.*#
..... ...*. .***.
Эдгээр жишээнд хоолойг '$ * $' тэмдэгтээр илэрхийлэв.
Танаас хотод яг нэг хоолой байрлахаар хэдэн төрлийн ялгаатай арга байгааг тооцоолдог програм бичихийг гуйжээ.
Хэрвээ 2 арга замын хоолойнуудын дор хаяж 1 квадрат нь ялгаатай байвал эдгээр 2 арга замыг хоорондоо ялгаатай гэж үзнэ.
Оролт
Эхний мөрөнд Бэрландын талбайн өндөрийн хэмжээ болон өргөний хэмжээ болох 2 бүхэл тоонууд $n, m$ ($2 ≤ n, m ≤ 2000$) өгөгдөнө.
Дараагийн $n$ ширхэг мөрний мөр болгон $m$ ширхэг тэмдэгт агуулна. Энэ нь хотын зураглал юм.
Хэрвээ зураглалын квадрат '$.$' тэмдэглэгдсэн байвал квадрат нь хоосон бөгөөд хоолойг бариж болно гэсэн үг.
Хэрвээ зураглалын квадрат '$#$' тэмдэглэгдсэн байвал квадрат нь дүүрэн бөгөөд хоолойг бариж болохгүй гэсэн үг.
Гаралт
Эхний мөрөнд хоолойг барих ялгаатай арга замын тоог нэг бүхэл тоогоор илэрхийлэн хэвлэнэ үү.
Орчуулсан: Энхлут
Жишээ тэстүүд
Оролт
3 3 ... ..# ...
Гаралт
3
Оролт
4 2 .. .. .. ..
Гаралт
2
Оролт
4 5 #...# #...# ###.# ###.#
Гаралт
4
Тэмдэглэл
Эхний жишээнд хоолойг барих 3-н арга зам байна (Хоолойн квадратууд нь '$ * $' тэмдэгтээр тэмдэглэгдсэн):
.*. .*. ...
.*# **# **#
.*. ... .*.