Sivilizasiya
Komputer oyununda "Sivilizasiya" versiyası 1-də dünya xəritəsi kvadratlara bölünmüş düzbucaqlı bir sahədən ibarətdir. Hər bir kvadrat müəyyən bir relyef növünə malikdir. Sadəlik üçün biz üç növ relyeflə məhdudlaşacağıq: çöl, meşə və su. Köçkün xəritə üzərində hərəkət edir və çöl ilə örtülmüş kvadrata keçmək üçün bir vaxt vahidi, meşəyə keçmək üçün isə iki vaxt vahidi tələb olunur. Su ilə örtülmüş kvadrata keçmək isə mümkün deyil.
Sizin bir köçkününüz var və siz bütün dünyanı mümkün qədər tez ələ keçirmək üçün şəhər tikmək üçün bir yer müəyyən etmisiniz. Köçkünü şəhər tikiləcək yerə aparan və ən az vaxt tələb edən marşrutu tapın. Hər bir addımda köçkün hazırda olduğu kvadratla ortaq tərəfi olan kvadrata keçə bilər.
Giriş verilənləri
Giriş faylında xəritənin ölçüləri olan iki təbii ədəd N və M verilir, bunlar 1000-dən çox deyil (N - xəritədəki sətirlərin sayı, M - sütunların sayı). Sonra köçkünün başlanğıc mövqeyinin koordinatları x və y verilir, burada x - xəritədəki sətirin nömrəsi, y - sütunun nömrəsi (1 ≤ x ≤ N, 1 ≤ y ≤ M), sətirlər yuxarıdan aşağıya, sütunlar soldan sağa nömrələnir. Sonra köçkünü aparmaq lazım olan kvadratın koordinatları eyni şəkildə verilir.
Daha sonra dünya xəritəsinin təsviri N sətir şəklində verilir, hər biri M simvolu ehtiva edir. Hər bir simvol ya "." (nöqtə) ola bilər, bu çölü göstərir, ya "W" meşəni göstərir, ya da "#" suyu göstərir. Başlanğıc və son kvadratların su olmadığı təmin edilir.
Çıxış verilənləri
Çıxış faylının birinci sətirində köçkünün hərəkəti üçün tələb olunan vaxt vahidlərinin sayını göstərin (çöl ilə örtülmüş kvadrata keçmək 1 vaxt vahidi, meşəyə keçmək 2 vaxt vahidi tələb edir). Çıxış faylının ikinci sətirində köçkünün marşrutunu təyin edən simvollar ardıcıllığını göstərin. Hər bir simvol aşağıdakı dörd simvoldan biri olmalıdır: "N" (yuxarı hərəkət), "E" (sağa hərəkət), "S" (aşağı hərəkət), "W" (sola hərəkət). Əgər belə marşrutlar bir neçədirsə, onlardan hər hansı birini göstərin.
Əgər başlanğıc kvadratından son kvadrata getmək mümkün deyilsə, -1 sayını göstərin.