J. Триминонууд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Даалуугаар хучих маш олон сонирхолтой бодлогууд байдаг билээ. Жишээ татан нэгэн сонирхолтой баримтыг авч үзье. Бидэнд $8 × 8$ хэмжээ бүхий энгийн шатрын хөлөг байх бөгөөд уг хөлгийн яг 2 нүдийг авч хаяв. Хамгийн сонирхолтой нь авч хаясан 2 нүд нь ижил өнгийн байвал бид $1 × 2$ хэмжээтэй даалуу ашиглан үр дүнгийн шатрын хөлгийн хучиж чадах бөгөөд эдгээр 2 нүд нь өөр өнгийн байвал ингэж хучих боломжгүй байдаг.

Петя даалуунуудаас залхсан ба иймд тэрээр нэгэн шатрын хөлөг (заавал $8 × 8$ байх албагүй) аван уг хөлгийнхөө хэсэг нүдийг авч хаяж триминонууд ашиглан уг хөлгийг хучихаар оролдох болжээ. Триминоууд гэдэг нь $1 × 3$ (эсвэл $3 × 1$ хэмжээтэй байж болно, учир нь триминонууд дурын байдлаар эргэж болно) хэмжээ бүхий тэгш өнцөгтүүд юм. Түүнчлэн триминонуудын 2 захын цэгүүд нь заавал цагаан өнгөтэй байх бөгөөд голын нүд нь хар өнгөтэй байдаг ажээ. Триминонуудыг шатрын хөлөг дээр тавьж болох бөгөөд ингэхдээ тэдгээрийн нүднүүд нь шатрын хөлгийн авч хаягдаагүй нүднүүдийнх нь өнгөтэй таарч байх ёстой юм. Мөн өнгөнүүд нь яг тохирч байх ёстой: хар өнгөтэй нүднүүд нь зөвхөн хар өнгөтэй нүднүүдийг хучих ба цагаан өнгөтэй нүднүүд нь зөвхөн цагаан өнгөтэй нүднүүдийг хучих ёстой. Триминонууд нь шатрын хөлгөөс илүү гарсан байж болохгүй бөгөөд хоорондоо давхацсан байж болохгүй юм. Түүнчлэн шатрын хөлгийн бүх авч хаягдаагүй нүднүүд нь заавал триминонуудаар хучигдсан байх ёстой.

Петя-д туслан хэрэв түүний шатрын хөлгийг өгөгдсөн аргаар триминонууд ашиглан хучих нь боломжтой бол триминонууд ашиглан хучих нэг боломжит хувилбар олж өгнө үү.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 1000$) өгөгдөх ба эдгээр нь шатрын хөлгийн хэмжээг илэрхийлнэ. Дараагийн $n$ мөрийн мөр болгонд $m$ ширхэг тэмдэгт өгөгдөх ба эдгээр нь шатрын хөлгийг илэрхийлнэ. Хэрэв зарим байрлал нь "."-ыг агуулж байвал уг нүдийг авч хаясан гэсэн үг юм. "w" тэмдэгт нь цагаан нүдийг, "b" тэмдэгт нь хар нүдийг илэрхийлнэ. Мөн авч хаясан нүднүүдийг нэмснээр зөв шатрын хөлөг үүснэ, өөрөөр хэлбэл хар цагаан нүднүүд ээлжилсэн байх юм. Гэхдээ ингэж үүссэн шатрын хөлөг нь энгийн хэмжээтэй биш байж болно.

Гаралт

Хэрэв дор хаяж нэг зөв хучилт оршин байвал эхний мөрөнд "YES" (хашилтгүйгээр) гэж хэвлэх ба дараа нь хучилтын тайлбарыг хэвлэнэ үү. Тайлбар нь $n$ ширхэг мөр агуулах мөр болгонд $m$ ширхэг тэмдэгт хэвлэнэ. Авч хаягдсан нүднүүд нь оролттой адилхан "."-аар тэмдэглэгдэнэ. Триминонуудыг тэмдэглэхдээ "a", "b", "c", "d" гэсэн тэмдэгтүүдийг ашиглах ба тримино бүрийн 3 нүд болгон нь заавал ижил тэмдэгтээр тэмдэглэгдсэн байна. Хэрэв 2 тримино ерөнхий талтай байвал тэдгээр нь заавал өөр тэмдэгтүүдээр тэмдэглэгдсэн байх ёстой. Харин ерөнхий талгүй 2 тримино ижил тэмдэгтүүдээр тэмдэглэгдсэн байж болно. Доорх жишээнүүдийг харна уу.

Хэрэв хөлгийг зөвөөр хучих олон тооны арга байвал та тэдгээрийн алийг нь ч хэвлэсэн болно. Хэрэв триминонуудыг ашиглан хучих боломжгүй эсвэл зөв байдлаар хучихын тулд "a", "b", "c", "d" гэсэн тэмдэгтүүд нь хангалттай байх хариулт оршин байхгүй бол эхний мөрөнд "NO" (хашилтгүйгээр) гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
6 10
.w.wbw.wbw
wbwbw.w.w.
bw.wbwbwbw
w.wbw.wbwb
...wbw.w.w
..wbw.wbw.
Гаралт
YES
.a.aaa.ccc
baccc.c.a.
ba.dddcbab
b.aaa.cbab
...bbb.b.b
..ccc.ddd.
Оролт
2 2
wb
bw
Гаралт
NO
Оролт
1 3
wbw
Гаралт
YES
bbb
Оролт
1 3
...
Гаралт
YES
...
Сэтгэгдлүүдийг ачааллаж байна...