Бат, Цэцэг хоёр хөлөгт тоглоом тоглож байна. Тоглоомын хөлгийг n×n хүснэгтээр дүрсэлж болно. Хүснэгтийн мөр багануудыг 1,2,…,n гэж дугаарласан байдаг ба арал болон далайг дүрсэлсэн байдаг. Арлаар зүүн, баруун, дээш эсвэл доош чиглэлд нэг нүдээр шилжиж болно. Хэрэв хуурай газрын нэг нүднээс нөгөө хуурай газрын нүд рүү нэг буюу хэд хэдэн алхмаар шилжиж болж байвал хоёр нүд холбогдсон гэж үзнэ. Тоглоомд хуурай газрыг тэмдэглэсэн нүднүүд хоорондоо холбогдож арал, усыг тэмдэглэсэн нүднүүд холбогдож далай үүсгэдэг. Арал нь далайгаар хүрээлэгдсэн. Иймээс хүснэгтийн эхний болон сүүлийн мөр, баганууд нь зөвхөн усны нүднүүд байна.
Бат, Цэцэг хоёр хөлөгт тоглоомоор тоглохдоо нэг нүднээс нөгөө нүд рүү хүрэхэд хамгийн цөөн нүүдлээр хэрхэн хүрэхийг тооцоолохоор шийдсэн. Тоглоомын хөлөг хэт том тул хүүхдүүд таныг шийдэж өгөхийг хүсэж байна.
Хүүхдүүд танаас q асуулга асуух ба та түүнд хариулах ёстой: (r1,c1) ба (r2,c2) нүднүүд өгөгдсөн бол эхний нүднээс хоёр дахь нүд рүү хүрэхэд хамгийн цөөндөө хэдэн алхам шаардлагатай вэ?
Эхний мөрөнд хоёр бүхэл тоо n ба q байна. Энэ нь хүснэгтийн хэмжээ болон асуулгын тоо.
Дараагийн n мөр бүрд хүснэгтийн нүдийг дүрсэлсэн n тэмдэгт байна. Энд "." нь ус, "#" нь хуурай газар болохыг заана.
Дараагийн q мөр бүрд дөрвөн бүхэл тоо: эхний нүдний мөр ба багана r1,c1, хоёр дахь нүдний мөр ба багана r2,c2 байна.
Асуулга бүрийн хариултыг мөр бүрд хэвлэнэ үү.
| № | Оноо | Хязгаарлалт |
|---|---|---|
| 1 | 17 | n≤200, q≤200 |
| 2 | 10 | Ямар ч мөр эсвэл баганад хуурай газрын нүдний хооронд усны нүд байхгүй |
| 3 | 28 | Аль ч мөрийн хувьд хуурай газрын нүднүүдийн хооронд усны нүд байхгүй |
| 4 | 45 | Нэмэлт хязгаарлалт байхгүй |
8 4 ........ ..####.. .##.###. .##.###. .#...... .#####.. ..#####. ........ 2 3 3 7 4 5 4 5 4 7 7 7 6 2 3 2
5 0 17 3
Эхний асуулгын хамгийн богино зам 5 алхам, гурав дахь асуулгынх 17 алхам байна. Ижил нүдний хоорондын зай 0.