АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

L-Морь (KnightL) бол L хэлбэрээр нүүдэг шатрын дүрс юм. 

Бид KnightL(a,b) гэдгээр  (x₁, y₁) байрлалаас (x₂, y₂) байрлалд хүрэх боломжит нүүдлүүдийн тоог тодорхойльё.

• x₂ = x₁ ± a , y₂ = y₁ ± b   юм уу
• x₂ = x₁ ± b , y₂ = y₁ ± a хэлбэрээр нүүнэ.

Энд (a, b) болон (b,a) гэсэн нүүдэл нь нэг ижил хэлбэрийн нүүдлүүд гэдгийг анзаараарай.

Жишээлбэл

5 х 5 хэмжээтэй шатрын хөлгийн төв дээр байгаа L-морины KnightL(2, 1) юм уу KnightL(1, 2)

гэсэн нүүдлүүд нь нэгэн төрлийн нүүдэл болох нь харагдаж байна.

Энэ нь аль нэг чиглэлд 2 нүд шилжээд, перпендикуляр чиглэлд 1 нүд шилжиж байгаа нь ажиглагдаж байна.

Өгөгдсөн n x n шатрын хөлгийн хувьд (a, b) хос бүрийн хувьд (1 <= a, b <n) L-морь KnightL(a, b) нүүдлээр 

(0, 0) байрлалаас  (n-1, n-1) байрлалд хүрэх хамгийн цөөн нүүдлийн тоог тодорхойлно уу?

Хэрвээ тухайн нүдэнд очих очих боломжгүй бол -1 байна. Тэгвэл (a, b) бүрийн хувьд KnightL(a, b) асуултанд хариулна уу?

Оролтын хэлбэр:

Шатрын хөлгийн хэмжээ болох n тоо өгөгдөнө.

Хязгаарлалт:

5 <= n <= 25

Гаралтын хэлбэр:

n-1 ширхэг мөр, n-1 ширхэг багананд бүх боломжит (i, j) –ийн хувьд Knight(i, j) нүүдлээр (n-1, n-1)

нүдэнд очих боломжит хамгийн цөөн нүүдлийн тоог (i, j)  нүдэнд хэвлэнэ үү?

Хэрвээ тухайн нүдэнд очих боломжгүй бол -1 гэж хэвлэнэ үү?

Жишээлбэл n = 3 үед боломжит (i, j) хосууд нь

(1, 1), (1,2)

(2,1), (2,2) гэсэн хэлбэртэй байна.

Жишээ оролт 0

5

Жишээ гаралт 0

4 4 2 8

4 2 4 4

2 4 -1 -1

8 4 -1 1

Тайлбар 0

Дараах зурган дээр KnightL(1, 1),  KnightL(1, 2), KnightL(1, 3) хэлбэрийн 

нүүдлүүдийг харуулсан байна.

Харин KnightL(1,4) хэлбэрийн нүүдлийн хувьд хамгийн цөөн нүүдлүүдийн нэг нь дараах хэлбэртэй байна.

(0 ,0) -> (1, 4) -> (2, 0) -> (3, 4) -> (4, 0) -> (0, 1) -> (4, 2) -> (0,3) -> (4,4) гэсэн дарааллаар буюу

хамгийн цөөндөө нийт 8 удаа нүүж тухайн нүдэнд очиж байна.

Тийм учраас гаралтын файлын эхний мөрөнд  KnightL(1, 1) = 4,  KnightL(1, 2) = 4, KnightL(1, 3) = 2, KnightL(1, 4) = 8

буюу 4 4 2 8 гэж хэвлэсэн байна.

Энэ мэтчилэн дараагийн нүднүүдэд тухайн (i, j) тооны буюу KnightL(i ,j) хэлбэрийн нүүдлээр очиж болох

хамгийн цөөн нүүдлийн тоонуудыг хэвлэнэ.

Жишээ нь

(0,0) байрлалаас KnightL(3, 3) байдлаар хэзээ ч (4, 4) нүдэнд очих боломжгүй учраас (3,3) нүдэнд -1 байна.

Орчуулсан : Хөвсгөл аймгийн Ирээдүй сургуулийн багш Д.Батмөнх