| Бодолт илгээх | Бүх бодолтууд | Шилдэг бодолтууд | Жагсаалт руу буцах |
MZO20131 - Поттер |
Гарри Поттер N x M хэмжээтэй тэгш өнцөгт хэлбэрийн агуй дахь Волдемортын нууц шүтээнийг олж авчээ. Одоо түүнд зомбинууд ирэхээс өмнө аль болох хурдан агуйгаас гарах шаардлагатай байгаа.
Агуй нь дөрвөн талаасаа ханаар хүрээлэгдсэн ба нэгж талбайтай квадрат нүднүүдээс тогтоно. Агуй нь К ширхэг гарцтай ба тэдгээрийн аль нэг рүү очиж байж гарна. Зарим нүднүүдэд чулуун багана байрлана. Поттер аль нэг нүднээс түүнтэй хөрш дөрвөн нүдний аль нэг сул (баганагүй) нүд рүү шилжиж чадна.
Агуйд мөн порталууд байх ба портал нь Поттерыг нэг нүднээс (порталын оролт) шууд өөр нэг нүд (порталын гаралт) рүү аваачиж чадна. Поттер порталын оролттой нүдэнд байхдаа түүнийг ашиглаж болно (гэхдээ заавал ашиглах албагүй).
Поттерын байгаа нүд мэдэгдэж байгаа бол түүнийг гаргах хамгийн богино замын уртыг ол (хамгийн цөөхөн нүднээс тогтох замын урт).
Input
Эхний мөрөнд агуйн хэмжээг илэрхийлэх N, M бүхэл тоонууд байрлана (2 ≤ N ≤ 100, 2 ≤ M ≤ 100). N нь мөрийн тоо, M нь баганын тоо.
Хоёр дахь мөрөнд Поттерын одоо байгаа нүдний байрлал болох X0, Y0 бүхэл тоонууд өгөгдөнө (1 ≤ X0 ≤ N, 1 ≤ Y0 ≤ M). Эхний тоо нь мөрийн дугаар, хоёр дахь тоо нь баганын дугаарыг заана. Мөрүүд дээрээс доош, баганууд зүүнээс баруун тийш дугаарлагдана.
Дараагийн N тооны мөр тус бүрт M тоо өгөгдөх ба агуйн доторх багануудын байрлалыг дараах байдлаар дүрсэлнэ: 0 – хоосон нүд, 1 – баганатай нүд.
Дараагийн мөрөнд порталуудын тоо болох P бүхэл тоо өгөгдөнө (0 ≤ P ≤ 1000).
Дараагийн P тооны мөр тус бүрд нэг портал X1, Y1, X2, Y2 бүхэл тоонуудаар өгөгдөнө (1 ≤ X1, X2 ≤ N, 1 ≤ Y1, Y2 ≤ M). Эдгээр тоонууд нь порталын оролт, гаралтын координатууд юм. Ямар ч хоёр порталын оролт давхцахгүй.
Дараагийн мөрөнд гарцын тоо болох K (1 ≤ K ≤ 10) бүхэл тоо өгөгдөнө.
Дараагийн К тооны мөрөнд гарцуудыг тодорхойлох X, Y бүхэл тоонууд өгөгдөнө (1 ≤ X ≤ N, 1 ≤ Y ≤ M).
Поттерын анхны байрлал баганатай эсвэл гарцтай нүдэнд байрлахгүйгээр өгөгдөнө. Порталын оролт, гаралт болон гарц нь баганатай нүдэнд байхгүй. Ямар ч порталын оролт нь гарцтай нүдэнд байхгүй.
Output
Хэрэв гарах боломжгүй бол Impossible гэсэн үгийг гаргана. Эсрэг тохиолдолд хамгийн богино замын уртыг (нүдний тоо) хэвлэнэ.
Example
Input:6 4
3 2
0 0 0 0
0 1 1 0
0 0 1 0
0 1 1 0
0 0 1 0
0 0 0 0
0
1
3 4 Output: 9
| Нэмсэн: | sw40 |
| Огноо: | 2013-05-07 |
| Хугацааны хязгаарлалт: | 1s |
| Эх кодын хэмжээний хязгаарлалт: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Програмчлалын хэлүүд: | Бүгд дараах хэлүүдээс бусад: ADA95 ASM64 BASH BF C++ 4.3.2 C99 CLPS CLOJURE D ERL FSHARP GO ICON ICK JS-RHINO LUA NEM NICE NODEJS OCAML PIKE PRLG-swi SCALA SCM guile SCM qobi SED ST TCL WHITESPACE |
hide comments
|
2019-04-04 10:01:39
BFS |
|
|
2015-12-22 19:44:34 erdenebayr_d
жишээ тестийн гаралт нь буруу юм байна гэж бодоод байсан чинь яг анх байгаа байрлал нь туулсан замын тоондоо нэмэгдэж байгаан байна |
|
|
2015-04-20 12:50:24 Bataa
6 4 4 1 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0 0 4 3 1 1 1 1 2 1 4 2 4 4 4 4 3 6 1 1 6 4 Last edit: 2015-04-20 12:52:02 |
|
|
2014-03-06 17:37:14 batorshih
zalusa portal deer yaj zohitsuulhuu help me |
--------
----------
