B. Роботуудыг тестлэх

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

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

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

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

Кибернетикүүдийн Алдаа (КА) байгууллага бомбын мэргэжилтэн роботын анхны загварыг бүтээсэн. Боломжит асуудлуудыг илрүүлэхийн тулд байгууллага цуврал тестүүдийг гүйцэтгэхээр шийдсэн. Тест бүрийн эхэнд загвар робот $x × y$ хэмжээтэй тэгш өнцөгт талбарын $(x_{0}, y_{0})$ нүдэнд байрлана. Үүний дараа талбарын аль нэг нүдэнд мина суулгана. Яг $x*y$ тест хийгдэх бөгөөд өмнө нь мина тавигдаагүй квадрат дээр тавигдах бүрт тест хийнэ. Роботын эхлэх нүд нь үргэлж ижил байна.

Талбар дээр обьектуудыг байрлуулсны дараа робот зөвхөн '$L$', '$R$', '$U$', '$D$' үсгүүдээс бүрдсэн $s$ тэмдэгт мөрд бичигдсэн командуудын дарааллын дагуу гүйх хэрэгтэй. Эдгээр командууд нь роботыг зүүн тийш, баруун тийш, дээшээ, доошоо нэг нүд хөдлөхыг заах ба хэрвээ өгөгдсөн чиглэлд хөдлөх боломжгүй бол байрандаа зогсохыг заана. Робот командуудын дарааллыг гүйцэтгэж дуусангуут кодон дахь алдааны улмаас мина дэлбэрнэ. Гэхдээ хэрвээ робот хугацааны нэг агшинд минатай ижил квадратад байвал кодон дахь алдаанаас болоогүй ч мина дэлбэрнэ.

Зүүн тийшээ хөдлөх нь $y$ координатыг бууруулах бол баруун тийш хөдлөх нь ихэсгэнэ. Үүнтэй адилаар дээшээ хөдлөх нь $x$ координатыг бууруулах бол доошоо хөдлөх нь ихэсгэнэ.

Тестүүд маш урт хугацаанд явагдаж болох тул таны ажил бол тэдгээрийн үр дүнг таамаглах юм. $0$-с $length(s)$ хүртэлх $k$ бүрийн хувьд таны ажил бол хэдэн тестээр робот мина дэлбэрэхээс өмнө яг $k$ командын дагуу гүйж чадах вэ гэдгийг олох юм.

Оролт

Оролтын эхний мөрөнд дөрвөн бүхэл тоон утга $x$, $y$, $x_{0}$, $y_{0}$ ($1 ≤ x, y ≤ 500, 1 ≤ x_{0} ≤ x, 1 ≤ y_{0} ≤ y$) байх буюу талбарын хэмжээ ба роботын эхлэх координат байна. $X$ тэнхлэг нь доош чиглэсэн бол $Y$ тэнхлэг нь баруун тийш чиглэсэн байна.

Хоёр дахь мөрөнд роботын гүйцэтгэх ёстой командуудын дараалал $s$-ийг агуулна. Энэ тэмдэгт мөр нь $1$-c $100 000$ тэмдэгтийн урттай байх ба зөвхөн '$L$', '$R$', '$U$', '$D$' тэмдэгтүүдээс бүрдэнэ.

Гаралт

$(length(s) + 1)$ тоонуудаас бүрдэх дарааллыг хэвлэ. Тэгээс эхлэн дугаарлах ба $k$-р байрлал дээр робот дэлбэрэхээсээ өмнө яг $k$ командын дагуу гүйх тестийн тоог хэвлэ.

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

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

Оролт
3 4 2 2
UURDRDRL
Гаралт
1 1 0 1 1 1 1 0 6
Оролт
2 2 2 2
ULD
Гаралт
1 1 1 1

Тэмдэглэл

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

Сэтгэгдлүүдийг ачааллаж байна...