C. Шорон ба чихэр

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

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

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

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

"Шорон ба чихэр" тоглоом ачааллаж байх үед та серверээс $k$ үеийн тайлбарыг авах шаардлагатай. Тайлбар бүр $n × m$ хэмжээтэй тэгш өнцөгт талбарын зураг байна. Талбарын зарим нүд нь чихэр агуулж болно (нүд бүр хамгийн ихдээ нэг чихэртэй байна). Зураг дээр хоосон нүдийг "$.$" тэмдэгтээр харин уг нүдэнд чихэр байвал Англи цагаан толгойн үсгээр тэмдэглэгдэнэ. Нэг үед төстэй чихрүүд байж болох ба энэ тохиолдолд зураг дээрх харгалзах нүднүүдийн үсэг нь адилхан байна.

Та сүлжээгээр мэдээлэл дамжуулахдаа ачааллыг бага байлгахыг хүсэх буюу дамжуулсан мэдээллийн нийт хэмжээг хамгийн бага байлгахыг хүснэ. Үеүүдийг дурын дарааллаар дамжуулж болно. Тухайн $A$ үеийг дамжуулах хоёр зам байна:

  1. Та $A$ үеийг бүхлээр нь дамжуулж болно. Ингэхдээ та сүлжээгээр $n*m$ байт дамжуулах хэрэгтэй.
  2. Та $A$ үе болон өмнө нь дамжуулагдсан $B$ (хэрвээ оршин байвал) үеүүдийн ялгааг дамжуулж болно; энэ үйлдэл нь $d_{A, B}*w$ байтыг дамжуулахыг шаардах ба энд $d_{A, B}$ нь $A$ болон $B$-н хувьд талбарын ялгаатай нүднүүдийн тоо ба $w$ нь тогтмол тоо байна. Та $d_{A, B}$ утгыг тооцоолохын тулд $A$ болон $B$ үеүүдийн нүднүүдийг л харьцуулах ёстой. Та үеүүдийн зургийг өөрчилж болохгүй буюу өөрөөр нэг нэгэнтэй нь харьцангуйгаар эргүүлж мөн шилжүүлж болохгүй.

Таны ажил бол бүх $k$ үеийг хамгийн бага ачаалалтайгаар дамжуулах аргыг олох юм.

Оролт

Эхний мөрөнд дөрвөн бүхэл тоон утга $n, m, k, w$ $(1 ≤ n, m ≤ 10; 1 ≤ k, w ≤ 1000)$ байна. Тэгээд $k$ үеийн тайлбар байна. Үе бүр $n$ мөрөөр тодорхойлогдох ба мөр бүр $m$ тэмдэгт агуулна. Тэмдэгт бүр Англи цагаан толгойн үсэг эсвэл цэг ("$.$") байна. Үсгийн том жижиг байгаа эсэх нь хамаатай байна.

Гаралт

Эхний мөрөнд дамжуулагдсан байтын шаардлагатай хамгийн бага тоог хэвлэ.

Тэгээд $k$ ширхэг хос бүхэл тоо $x_{1}, y_{1}, x_{2}, y_{2}, ..., x_{k}, y_{k}$ хэвлэх ба эдгээр нь үеүүдийг дамжуулах замыг тодорхойлно. $x_{i}$, $y_{i}$ хос нь $x_{i}$ үе нь $y_{i}$ замаар дамжуулагдах шаардлагатайг илэрхийлнэ. Хэрвээ $y_{i}$ нь 0-тэй тэнцүү бол уг үе нь эхний замыг ашиглан дамжуулагдсан гэсэн үг бол бусад тохиолдолд $y_{i}$ нь өмнөх дамжуулагдсан үеийн дугаартай тэнцүү байна. Энэ нь та $x_{i}$ үеийг дамжуулахын тулд $y_{i}$ ба $x_{i}$ үеүүдийн ялгааг дамжуулна гэсэн үг. Хос тоонуудыг үеүүдийг дамжуулах дарааллаар хэвлэнэ. Үеүүд оролтонд өгөгдсөн дарааллаараа 1-c $k$ хүртэл дугаарлагдана.

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

Орчуулсан: Г.Мэндбаяр

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

Оролт
2 3 3 2
A.A
...
A.a
..C
X.Y
...
Гаралт
14
1 0
2 1
3 1
Оролт
1 1 4 1
A
.
B
.
Гаралт
3
1 0
2 0
4 2
3 0
Оролт
1 3 5 2
ABA
BBB
BBA
BAB
ABB
Гаралт
11
1 0
3 1
2 3
4 2
5 1
Сэтгэгдлүүдийг ачааллаж байна...