B. Инна ба шинэ чихэртэй матриц

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

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

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

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

Инна амттан болон "Чихэртэй Матриц" гэх тоглоомд дуртай юм. Өнөөдөр тэрээр "Чихэртэй Матриц 2: дахин шинэчлэлт" гэх шинэ тоглоомтой иржээ. Шинэ тоглоомын талбар нь $n × m$ хэмжээ бүхий тэгш өнцөгт хэлбэртэй хүснэгт байв. Хүснэгтийн мөр болгон нь одойн барималтай нэг нүд, чихэртэй нэг нүд агуулах ба уг мөрийн бусад нүднүүд нь хоосон байна. Тоглоом дуусах хүртэл хэд хэдэн нүүдэл хийх юм. Нүүдэл болгонд тоглогч одой нь чихэртэй нүдэн дээр байрлаагүй байх уг матрицын бүх мөрүүдийг сонгох бөгөөд "Явцгаая!" гэж орилно. Үүний дараа сонгогдсон мөрүүдийн бүх одойнууд нэг зэрэг баруун тийш хөдөлж эхэлнэ. Секунд болгонд одой бүр нь өөрийн байрлаж буй нүдний баруун талд байрлах зэргэлдээ нүд уруу нүүнэ. Уг одойнуудын нүүдэл нь дараах үйл явдлуудын нэг нь болтол үргэлжлэх юм:

  • сонгогдсон мөрүүдийн аль нэг одой нь өөрийн байрлах мөрийн хамгийн баруун талын нүдэнд очих;
  • сонгогдсон мөрүүдийн аль нэг одой чихэртэй нүдэнд очих.

Уг тоглоомын зорилго нь бүх одойнуудыг чихэртэй нүдэнд аваачих юм.

Инна ер бусын нэгэн бөгөөд тэрээр ийм сонирхолтой тоглоомтой хичээлдээ иржээ. Харин таны тухайд? Таны даалгавар бол уг тоглоомыг ухаалгаар тоглох юм. Дэлгэрэнгүй хэлбэл та тоглоомын талбар өгөгдсөн байхад тоглогч уг тоглоомын зорилгыг биелүүлэхэд шаардагдах хамгийн бага үйлдлийн тоог хэлж өгөх юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ $(1 ≤ n ≤ 1000; 2 ≤ m ≤ 1000)$ өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгонд $m$ ширхэг тэмдэгт өгөгдөнө. Эдгээр нь "Чихэртэй Матриц 2: дахин шинэчлэлт" тоглоомын талбарыг илэрхийлнэ. "$*$" тэмдэгт нь талбарын хоосон нүдийг илэрхийлнэ, "$G$" тэмдэгт нь одойг илэрхийлэх ба "$S$" тэмдэгт нь чихрийг илэрхийлнэ. Матриц нь эдгээрээс өөр тэмдэгт агуулаагүй байна. Мөн мөр болгон нь яг нэг ширхэг "$G$" болон нэг ширхэг "$S$" тэмдэгт агуулсан байх юм.

Гаралт

Дан мөрөнд тоглоомын зорилгыг биелүүлэхэд шаардагдах хамгийн бага үйлдлийг тоог хэвлэнэ үү. Хэрэв биелүүлэх боломжгүй бол $-1$ гэж хэвлэнэ үү.

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

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

Оролт
3 4
*G*S
G**S
*G*S
Гаралт
2
Оролт
1 3
S*G
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...