Robot Naviqasiyası#2756

Robot Naviqasiyası

1 saniyə

64 meqabayt

Çox asan

Robot uzaq bir planetin araşdırılması üçün göndərilib. Robotun izləməli olduğu yolu müəyyən etmək üçün hər gün bir proqram göndərilir. Bu proqram aşağıdakı əmrlərdən ibarətdir:

FORWARD: bir vahid irəli hərəkət et.
TURN LEFT: $90$ dərəcə sola dön. Robot eyni nöqtədə qalır.
TURN RIGHT: $90$ dərəcə sağa dön. Robot eyni nöqtədə qalır.

Robot ətraf mühitinin xəritəsini əldə etməyə imkan verən sensorlarla təchiz olunub. Xəritə $M$ sətir və $N$ sütundan ibarət bir tor kimi təsvir olunur. Hər bir tor nöqtəsi $(r, c)$ koordinatları ilə göstərilir, burada $r = 0$ r = 0 şimal kənarı, $r = M - 1$ r = M - 1 cənub kənarı, $c = 0$ c = 0 qərb kənarı və $c = N - 1$ c = N - 1 isə şərq kənarıdır. Bəzi tor nöqtələrində təhlükələr (məsələn, kraterlər) var, proqram bu nöqtələrdən yayınılmalıdır, əks halda robot itirilə bilər.

Əgər robotun ilkin mövqeyi və istiqaməti, həmçinin təyinat nöqtəsi məlumdursa, bizim məqsədimiz robotu təyinat nöqtəsinə aparan ən qısa (əmrlərin sayına görə ən az) proqramı göndərməkdir (təyinat nöqtəsində hansı istiqamətlə dayanması vacib deyil). Siz isə robotu təyinat nöqtəsinə aparan müxtəlif ən qısa proqramların sayına maraqlanırsınız, çünki planetlərarası ünsiyyət həmişə etibarlı olmur və fərqli ardıcıllıqlar göndərmək lazım ola bilər. Ən qısa proqramların sayı çox böyük ola bilər, ona görə də, Çin Qalıq Teoreminin son cavabı hesablamağa imkan verdiyini bilmək şərtilə, yalnız müəyyən verilmiş modul üzrə qalıq sizi qane edir.

Giriş

Girişdə bir neçə hal verilir. Hər halın ilk sətrində üç tam ədəd $M$ , $N$ və modul $m$ ( $0 < M, N \leq 1000$ 0 < M, N \leq 1000, $0 < m \leq 1000000000$ 0 < m \leq 1000000000) verilir. Növbəti $M$ sətrin hər birində $N$ simvol verilir və xəritəni təsvir edir. '.' robotun daxil ola biləcəyi tor nöqtəsini, '*' isə təhlükəni göstərir. Hər bir halın son sətrində isə dörd tam ədəd $r_{1}$ r_1, $c_{1}$ c_1, $r_{2}$ r_2, $c_{2}$ c_2 və bir simvol $d$ verilir. Koordinatlar $(r_{1}, c_{1})$ (r_1, c_1) başlanğıc mövqeyini, $(r_{2}, c_{2})$ (r_2, c_2) təyinat nöqtəsini, $d$ isə başlanğıc istiqamətini ('N', 'S', 'W', 'E' simvollarından biri) göstərir. Qəbul edilir ki, başlanğıc və təyinat nöqtələri təhlükəli deyil. Giriş $m = 0$ m = 0 olduqda bitir.

Çıxış

Hər bir hal üçün aşağıdakı formatda bir sətirdə halın nömrəsini, modulu və robotu təyinat nöqtəsinə apara bilən fərqli ən qısa proqramların sayının $m$ -ə görə qalıqını çap edin. Əgər robotu təyinat nöqtəsinə apara bilən heç bir proqram yoxdursa, proqramların sayını -1 olaraq çıxarın.

Nümunələr

Nümunə 1