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

Гридланд хотыг n x m матрицаар дүрсэлсэн бөгөөд мөрүүдийг нь 1–ээс n хүртэл,  багануудыг нь 1-ээс m

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

шулуун байдлаар дүрслэгдэнэ.

Өөрөөр хэлбэл  төмөр замын эхлэл болон төгсгөл нь (r, c1) болон (r, c2) байх ба r нь мөрийн дугаар, c1 - эхлэх цэгийг,

c2 - төмөр замын дуусах цэгийг заана.

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

Гэрлийн шон нь төмөр зам байхгүй аль ч нүдэнд байж болно.

Гридланд хотын газрын зураг болон төмөр зам k өгөгдөнө. 

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

Санамж :

Нэг мөр дээр хэд хэдэн төмөр зам салангид болон огтлолцон байрлаж болно.

Жишээлбэл

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

k = 3

r              c1            c2

1              1              4

2              2              4

3              1              2

4              2              3

Гэвэл дараах map -ыг бий болгоно.

Энэ тохиолдолд гэрлийн шон байрлуулж болох 5 хоосон цэг байна. (улаан)

Функцын тодорхойлолт

gridlandMedtro функцыг гүйцээж бич. Гэрлийн шон байрлуулж болох нийт боломжит цэгүүдийг илэрхийлсэн integer утга буцаана.

Параметрүүд :

 n : нийт мөрийн тоо, integer

 m : баганы тоо, integer

 k : төмөр замын тоо, integer

track : 2 хэмжээст integer хүснэгт, элемент бүр мөр, эхлэх багана, дуусах баганыг илэрхийлсэн 3 integer утга агуулсан байна.

Оролтын формат

Эхний мөрөнд зайгаар тусгаарлагдсан 3 integer тоо өгөгдөнө.

n, m болон k.  мөрийн тоо, баганы тоо, төмөр замын тоог илэрхийлнэ.

Дараагийн к тооны мөр болгонд зайгаар тусгаарлагдсан 3 integer тоо өгөгдөнө.

r, c1, c2. мөрийн дугаар, төмөр замын эхлэх, дуусах цэгийн дугаар

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

 1 <= n, m <= 10⁹

0 <= k <= 1000

1 <= r <= n

1 <= c1 <= c2 <= m

Гаралтын формат :

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

Жишээ

Оролт

4 4 3

2 2 3

3 1 4

4 4 4

Гаралт

9

Тайлбар 

Дээрх хүснэгтэд шараар 1-р төмөр замыг, ногооноор 2 дахь , хөх өнгөөр 3 дахь төмөр замыг илэрхийлнэ.

Гэрлийн шонг аль ч улаан цэг дээр байрлуулж болно.

Орчуулсан : Б.Баясгалантөгөлдөр АНУ