J. Цэвэрлэгч Робот

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

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

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

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

Маша саяхан цэвэрлэгч робот худалдан авчээ. Тэр нь хэн нэгний туслалцаагүйгээр өрөөний шалыг цэвэрлэж чаддаг.

Маша-ын өрөө нь $w × h$ тэгш өнцөгт хэлбэртэй бөгөөд $1 × 1$ хэмжээтэй квадрат нүднүүдээс тогтдог. Өрөөний нүд болгон нь хоосон ('$.$' тэмдэгтээр илэрхийлнэ) эсвэл тавилгатай ('$*$' тэмдэгтээр илэрхийлнэ) байх юм.

Цэвэрлэгч робот нь өөрөө нэг хоосон нүд эзэлнэ. Өөрөөр хэлбэл тэрээр нэг нүдэн дээр байрлах юм. Мөн робот нь чиглэлтэй (4-н сонголтын нэг байна) ба бид түүнийг уг чиглэл уруу харж байна гэж хэлнэ.

Роботын хөдлөх болон өрөөний шал цэвэрлэх алгоритм нь дараах байдалтай байна:

  1. робот өөрийн байрлаж буй нүдээ цэвэрлэнэ;
  2. хэрэв роботын харж буй чиглэлд зэргэлдээ талтай нүд оршин байх ба хоосон байвал уг нүд уруу нүүж 1-р алхам уруу шилжинэ;
  3. Бусад тохиолдолд цагийн зүүний дагуу 90 градус эргэн (одоогийн чиглэлтэйгээ харьцангуй баруун тийш) 2-р алхам уруу шилжинэ.

Цэвэрлэгч робот нь Маша түүнийг унтраах хүртэл уг алгоритмыг гүйцэтгэсээр байх юм.

Та Маша-ын өрөөний тавилгын байрлал, цэвэрлэгч роботын анхны байрлал болон чиглэлийг мэдэж байгаа. Тэгвэл та хэрэв цэвэрлэгч робот нь хязгааргүй удаан ажиллана гэвэл түүний өрөөг цэвэрлэх нийт талбайг тооцоолж чадах уу?

Оролт

Эхний мөрөнд Маша-ын өрөөний хэмжээ болох 2 бүхэл тоо $w$ болон $h$ $(1 ≤ w, h ≤ 10)$ өгөгдөнө.

Дараагийн $w$ мөрийн мөр болгонд өрөөг илэрхийлэх $h$ тэмдэгтүүд өгөгдөнө. Хэрэв өрөөний нүд хоосон байвал '$.$' тэмдэгт харгалзана. Хэрэв өрөөний нүдэнд тавилга байрласан байвал '$*$' тэмдэгт харгалзана. Хэрэв өрөөгийн нүдэнд робот байрлаж байвал уг нүдэнд тавилга байхгүй ба цэвэрлэгч роботын чиглэлийг илэрхийлэх '$U$', '$R$', '$D$' эсвэл'$L$' үсэг харгалзана. Өрөөний бүтцийн дагуу '$U$' үсэг нь робот дээш харсныг, '$R$' үсэг нь робот баруун тийш харсныг, '$D$' үсэг нь робот доош харсныг '$L$' үсэг нь робот зүүн тийш харсныг илэрхийлнэ.

Оролтын $w$ мөрөнд '$U$', '$R$', '$D$' эсвэл '$L$' үсэг нь яг нэг удаа өгөгдөнө. Роботын анх байрлах нүд нь хоосон буюу ямар ч тавилгагүй байна.

Гаралт

Эхний мөрөнд хэрэв цэвэрлэгч робот нь хязгааргүй удаан ажиллана гэвэл түүний өрөөг цэвэрлэх нийт талбай болох ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
2 3
U..
.*.
Гаралт
4
Оролт
4 4
R...
.**.
.**.
....
Гаралт
12
Оролт
3 4
***D
..*.
*...
Гаралт
6

Тэмдэглэл

Эхний жишээнд робот эхлээд дээш нүүх гэж оролдох боловч тэрээр чадахгүй. Иймээс баруун тийш эргэнэ. Дараа нь баруун тийш 2 алхам хийх ба хананд тулах тул доош эргэнэ. Робот доош нүүх ба уг нүдээ цэвэрлэсний дараа зүүн тийш эргэнэ. Тэгээд зүүн тийш нүүх гэж оролдох боловч тавилга байгаа тул дээш эргэнэ. Ингээд дээш нүүн $(1, 3)$ нүдэнд ирэх ба дээш нүүж болохгүй тул баруун тийш эргээд, дахин доош эргээд $(2, 3)$ нүд уруу явах гэх мэт энэ үйлдэл давтагдах юм. Зурагт роботын очсон нүднүүдийг саарал өнгөөр тэмдэглэв.

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