C. Эрдэнэсийн тойрог

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

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

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

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

Танд тэгш өнцөгт хүснэгт хэлбэртэй газрын зураг байна. Хүснэгтийн нүд бүр нь саад, эсвэл тодорхой үнэ бүхий эрдэнэ, эсвэл бомб, эсвэл хоосон нүд байна. Мөн таны анхны байрлал танд өгөгдөнө.

Та газрын зураг дээрх нэг нүднээс хөрш нүдрүү явж болно. Энд та газрын зургийн хүрээг давж гарахгүй, мөн эрдэнэс, саад, бомбтой нүдрүү орох боломжгүй. Эрдэнэсүүдийг авахын тулд та битүү зам бүтээх ёстой (эхлэх цэгээс эхэлж эхлэх цэгт дуусах зам). Битүү зам нь бомбтой нүд агуулах ёсгүй. Битүү замын дотор орших эрдэнэсүүдийн үнэний нийлбэрийг $v$ мөн та уг замаар явж байхдаа $k$ ширхэг энгийн үйлдэл (нэг нүднээс нөгөөрүү шилжих) хийсэн гэе, тэгвэл энэ зам танд $v - k$ рублийн ашиг авчирна.

Таны ажил бол хамгийн их ашиг авчрах ямар ч бомб агуулаагүй битүү замыг байгуулах юм.

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

  1. Хүснэгтийн нүднүүдийг хавтгай дээрх цэгүүд гэе (хүснэгтийн $i$-р мөр $j$-р баганын огтлолцол дээр байгаа нүд нь $(i, j)$ цэг болно). Өгөгдсөн зам нь эдгээр цэгүүдийг дайрсан хэрчмүүд байна.
  2. Та хэрчмүүдийн дайраагүй, хүснэгтийн $p$ цэгийг хэрчмүүдийн дотор оршиж буй эсэхийг олох хэрэгтэй.
  3. Хүснэгтийн бусад цэгтэй огтлолцоогүй $p$ цэгээс эхлэсэн цацраг зурья (ийм цацраг оршин байна).
  4. Зурсан цацрагтай хэдэн хэрчим огтлолцож байгааг тоольё. Хэрвээ энэ тоо нь сондгой байвал бид $p$ цэгийг (буюу хүснэгтийн нүд) хэрчмүүдийн (замын) дотор байна гэж үзнэ. Бусад тохиолдолд бид энэ цэгийг гадна байна гэж үзнэ.

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$ $(1 ≤ n, m ≤ 20)$ байх буюу хүснэгтийн хэмжээ юм. Дараагийн $n$ мөр бүрт $m$ тэмдэгт байх буюу хүснэгтийн тодорхойлолт байна. Тодорхойлолт нь дараах зүйлсийг илэрхийлнэ:

  • "$B$" бол бомбтой нүд;
  • "$S$" бол эхлэх цэг ба та үүнийг хоосон нүд гэж үзэж болно;
  • $c$ ($1-8$) бол $c$ дугаартай эрдэнэс;
  • "$.$" бол хоосон нүд;
  • "$#$" бол саад.

Газрын зурагт $t$ эрдэнэс байна гэе. Тэгвэл дараагийн $t$ мөрд эрдэнэсүүдийн үнэ байна. $i$-р мөрөнд $i$ дугаартай эрдэнэсийн үнэ $v_{i}$ $( - 200 ≤ v_{i} ≤ 200)$ байна. Эрдэнэсүүд 1-с $t$ хүртэл дугаарлагдах нь тодорхой. Газрын зурагт 8-с их биет байхгүй нь бас тодорхой. Мөн газрын зурагт нэг л "$S$" тэмдэгт байна.

Гаралт

Таны олж чадах хамгийн их ашгийг илэрхийлэх нэг бүхэл тоог хэвлэ.

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

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

Оролт
4 4
....
.S1.
....
....
10
Гаралт
2
Оролт
7 7
.......
.1###2.
.#...#.
.#.B.#.
.3...4.
..##...
......S
100
100
100
100
Гаралт
364
Оролт
7 8
........
........
....1B..
.S......
....2...
3.......
........
100
-100
100
Гаралт
0
Оролт
1 1
S
Гаралт
0

Тэмдэглэл

Эхний жишээний хариулт дараах байдалтай харагдана.

Хоёр дахь жишээний хариулт дараах байдалтай харагдана.

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

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

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