D. Солитер

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

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

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

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

Вася-д $54$ хөзөртэй ($52$ ширхэг энгийн хөзрүүд болон 2 ширхэг хөзрийн хүн) нэг багц хөзөр байжээ. Тухайн мөчид Вася-д зөвхөн энэ л байв. Уйдаж үхэхгүйн тулд тэрээр эдгээр хөзрүүдээр солитер тоглохоор болжээ.

Вася $nm$ ширхэг хөзрийг $n × m$ хэмжээтэй тэгш өнцөгт хэлбэртэйгээр дэлгэж байрлуулах ажээ. Хэрэв эдгээр дэлгэж тавьсан хөзрүүд дунд хөзрийн хүмүүс (1 болон 2-р хүн) байвал Вася тэдгээрийг үлдсэн $54 - nm$ ширхэг хөзрүүдийн заримаар солих ба ингэснээр $nm$ ширхэг хөзөр дотор ямар ч хөзрийн хүн байхгүй болох юм. Түүнчлэн Вася хөзрийн хүнийг солихдоо дурын байдлаар хөзөр сонгон сольж болно. Уг багц хөзөр дотор хөзөр болгон яг нэг ширхэг байгааг анхаарна уу. Вася уг солитер нь шийдэгдсэн байхаар хөзрийг солих байв.

Хэрэв хөзрийг хүмүүсийг өөр хөзрөөр сольсоны дараа доторх хөзрүүд бүгд нэг өнгийн эсвэл бүгд хос хосоороо ялгаатай байх хоорондоо үл давхцах 2 ширхэг $3 × 3$ хэмжээтэй квадратууд оршин байвал Вася уг солитерийг шийдэгдсэн байна гэж үзэх юм.

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

Оролт

Эхний мөрөнд бүхэл тоо $n$ болон $m$ ($3 ≤ n, m ≤ 17$, $n × m ≤ 52$)-ууд өгөгдөнө. Дараагийн $n$ мөрийн мөр болгонд $m$ ширхэг үг өгөгдөнө. Үг болгон нь 2 үсгээс тогтоно. Хөзрийн хүмүүсийг харгалзан "J1" болон "J2" гэж тэмдэглэх юм. Бусад хөзрүүдийг тэмдэглэхдээ эхлээд хөзрийн үсгийг дараа нь хөзрийн өнгийг тэмдэглэнэ. Боломжит үсгүүд нь: "2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K" болон "A" байх бөгөөд боломжит өнгүүд нь: "C", "D", "H" болон "S" байх юм. Мөн бүх хөзрүүд нь ялгаатай байна.

Гаралт

Хэрэв солитер нь шийдэгдэж болох бол эхний мөрөнд хашилтгүйгээр "Solution exists." гэж хэвлэнэ үү. 2-дахь мөрөнд ямар аргаар хөзрийн хүмүүсийг солихыг хэвлэнэ үү. Түүнчлэн 3-н хувилбар байна:

  • Хэрэв оролтод өгөгдсөн мэдээлэл дотор ямар ч хөзрийн хүн байхгүй бол "There are no jokers." гэж хэвлэнэ үү.
  • Хэрэв нэг ширхэг хөзрийн хүн байх бөгөөд түүний дугаар нь $x$ байх ба $y$ нь уг хүнтэй солигдох хөзөр бол "Replace J$x$ with $y$." гэж хэвлэнэ үү.
  • Хэрэв 2 хөзрийн хүн нь 2-уулаа оролтод өгөгдсөн байвал "Replace J1 with $x$ and J2 with $y$." гэж хэвлэнэ үү. Энд $x$ болон $y$ нь харгалзан 1 болон 2-р хөзрийн хүнтэй солигдох ялгаатай хөзрүүдийг илэрхийлэх юм.

3-дахь мөрөнд эхний $3 × 3$ квадратын зүүн дээд булангийн координатуудыг "Put the first square to ($r$, $c$)." гэсэн хэлбэртэйгээр хэвлэх бөгөөд энд $r$ болон $c$ нь зүүн дээд булангийн нүдний харгалзан мөр болон баганыг илэрхийлнэ. Мөн ижил байдлаар 4-дэх мөрөнд 2-дахь $3 × 3$ квадратыг "Put the second square to ($r$, $c$)." хэлбэртэйгээр хэвлэнэ.

Хэрэв хэд хэдэн шийдэл байвал тэдгээрийн алийг нь ч хэвлэсэн болно.

Хэрэв ямар ч шийдэл оршин байхгүй бол дан мөрөнд хашилтгүйгээр "No solution." гэж хэвлэнэ үү.

Гаралтын хэлбэрийг илүү сайн ойлгохын тулд жишээнүүдийг сайн харна уу.

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

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

Оролт
4 6
2S 3S 4S 7S 8S AS
5H 6H 7H 5S TC AC
8H 9H TH 7C 8C 9C
2D 2C 3C 4C 5C 6C
Гаралт
No solution.
Оролт
4 6
2S 3S 4S 7S 8S AS
5H 6H 7H J1 TC AC
8H 9H TH 7C 8C 9C
2D 2C 3C 4C 5C 6C
Гаралт
Solution exists.
Replace J1 with 2H.
Put the first square to (1, 1).
Put the second square to (2, 4).
Оролт
4 6
2S 3S 4S 7S 8S AS
5H 6H 7H QC TC AC
8H 9H TH 7C 8C 9C
2D 2C 3C 4C 5C 6C
Гаралт
Solution exists.
There are no jokers.
Put the first square to (1, 1).
Put the second square to (2, 4).

Тэмдэглэл

Жишээ тестүүд нь бүх боломжит гаралтын хэлбэрүүдийг харуулсан байна.

Сэтгэгдлүүдийг ачааллаж байна...