B. Зүлэг тэгшлэгч

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

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

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

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

Танай цэцэрлэг өвс, хогийн ургамлаар дүүрэн байна. Танай цэцэрлэг дээрээсээ доошоо $1$-ээс $n$ хүртэл эрэмбэлэгдсэн эгнээ, зүүнээсээ баруун $1$-ээс $m$ хүртэл дугаарлагдсан багануудтай $n × m$ хэмжээтэй сараалжин хашаагаар дүрслэгднэ. Нүд тус бүр нь хос $(r, c)$-аар ялгарах ба энэ нь тухайн нүд нь $r$ дахь эгнээний $c$ дахь баганад байна гэсэн үг юм. Нүд тус бүр нь өвс, зэрлэг ургамлын аль нэгийг нь агуулж болно. Жишээ нь $4 × 5$ хэмжээтэй цэцэрлэг дараах байдлаар харагдаж болно (хоосон нүднүүд нь өвс байгааг илэрхийлнэ):

Танд бүх хогийн ургамлуудыг тайрах зүлэг тэгшлэгч байгаа. Эхэндээ та өвс тэгшлэгчээ барин цэцэрлэгийн зүүн дээд буланд зогс байна. Энэ нь $(1, 1)$ нүд юм. Та хаана ч зогсч байсан зүүн, баруун гэсэн хоёр чиглэлийн аль нэгийг сонгоно. Эхлээд та баруун тийш эргэнэ.
Нэг хөдөлгөөнөөрөө та дараах өгөгдлийн аль нэгийг хийнэ:

1) Өөрийн харж буй чиглэлд нэг нүд яв.

  • Хэрэв та баруун тийш харж байвал $(r, c)$ нүднээс $(r, c + 1)$ нүд рүү нүү.

  • Хэрэв та баруун тийш харж байвал $(r, c)$ нүднээс $(r, c - 1)$ нүд рүү нүү.

2) Нэг нүд доошил ($(r, c)$ нүднээс $(r + 1, c)$) нүд рүү). Дараа нь эсрэг талын нүд рүү чиглэлээ өөрчил.

  • Хэрэв та баруун тийш харж байсан бол зүүн тийш харна.

  • Хэрэв та зүүн тийш харж байсан бол баруун тийш харна.

Та цэцэрлэгийг орхиж болохгүй. Таны зүлэг тэгшлэгчээ барин зогсч байсан нүдэнд зэрлэг ургамал байвал та зэрлэг ургамлыг тайрна (харж буй зүгээсээ үл хамааран). Энэ үйлдлийг нүүдэл гэж үзэхгүй.
Бүх хогийн ургамлыг тайрахын тулд та хамгийн багадаа хэдэн нүүдэл хийх шаардлагатай вэ?

Оролт

Энхий мөр нь $n$ болон $m$ ($1 ≤ n, m ≤ 150$) гэсэн хоёр бүхэл тоо агуулах ба эдгээр нь эгнээний болон мөрний тоог тус тус харуулна. Дараагийн $n$ мөрүүд нь тус бүртээ $m$ тэмдэгтүүд агуулах ба энэ нь сараалжин хашааны агууламжийг илтгэнэ. "G" гэдэг нь тус нүд нь өвс агуулахыг илэрхийлэх бол "W" нь хогийн ургамал байгааг харуулна.

Хашааны зүүн дээд нүдэнд өвс байна.

Гаралт

Бүх хогийн ургамлыг тайрахын тулд та хамгийн багадаа хэдэн нүүдэл хийх шаардлагатайг харуулсан нэг тоог хэвлэнэ үү.

Орчуулсан: Энхгэрэл

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

Оролт
4 5
GWGGW
GGWGG
GWGGG
WGGGG
Гаралт
11
Оролт
3 3
GWW
WWW
WWG
Гаралт
7
Оролт
1 1
G
Гаралт
0

Тэмдэглэл

Эхний жишээнд буй зураг нь сараалжин хашааны анхны байлдыг харуулж байна.

Хогийн ургамлыг тайрах боломжит аргы дараах байдлаар үзүүлж байна.

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