SPOJ in Armenian

Շատ դժվար ծրագրավորման խնդիրներ լուծելուց հետո, Կարենը որոշեց խաղալ գլուխկոտրուկ մի խաղ: Անհրաժեշտ է գրել ծրագիր, որը կօգնի Կարենին հեշտությամբ լուծել գլուխկոտրուկը:

Խաղը կոչվում է Շարժական Լաբիրինթ, այն խաղում են R տող և C սյուն ունեցող խաղատախտակի վրա: Խաղատախտակի ամեն վանդակի կենտրոնում կա սև կետ և հորիզոնական կամ ուղղահայաց գծեր դեպի տվյալ վանդակի հարևան վանդակները հյուսիս, հարավ, արևելք, արևմուտք ուղղություններով: Հորիզոնական և ուղղահայաց գծերը կարող են բացակայել կամ միացված լինել հարևանների մի մասին: Ձեր առաջադրանքն է տեղափոխել խաղաքարը (i1, j1) վանդակի միջնակետից մինչև (i2, j2) վանդակի միջնակետ՝ շարժվելով միայն գոյություն ունեցող հորիզոնական և ուղղահայաց գծերով:

Անհրաժեշտ է հասնել վերջնակետին մինիմալ քայլերի միջոցով, որտեղ քայլը  բաղկացած է հետևյալ երկու մասերից: Առաջին, ամեն քայլում կարելի է ընտրել որևէ վանդակ և այն պտտել 90 աստիճան ժամսլաքի կամ ժամսլաքի հակառակ ուղղությամբ: Երկրորդ, ամեն քայլում խաղաքարը կարելի է տեղափոխել ընթացիկ վանդակից հարևան վանդակ, շարժվելով միայն հորիզոնական և ուղղահայաց գծերով: Այսինքն A վանդակից կարելի է անցնել հարևան B վանդակը, եթե A-ն ունի սև գիծ միացված B-ին և հակառակը: Քայլի ընթացքում այդ երկու գործողություններից որևէ մեկը կարող է բացակայել:

Մուտք

Մուտքի առաջին տողում գրված են R, C ամբողջ թվերը (1≤ R, C≤ 20): Հաջորդ տողում գրված են  i₁, j₁, i₂, j₂  թվերը, հետևյալ սահմանափակումներով՝ 1≤  i₁, i₂ ≤  R և 1≤  j₁, j₂≤ C:

Հաջորդ R տողերից յուրաքանչյուրը պարունակում է ճիշտ C բառ, բաժանված բացակներով, ամեն վանդակին համապատասխանեցնելով մեկ բառ ձախից աջ հերթականությամբ: Բառը ունի հետևյալ կառուցվածքը.

• Այն պարունակում է մեկ սիմվոլ՝ x, այս դեպքում վանդակը չունի հարևաններին միացնող գծեր:
• Կամ բառը պարունակում է N, E, S, W սիմվոլների մի մասը կամ բոլորը, որոնք համապատասպանաբար նշանակում են վանդակը միացված է գծով հյուսիս, արևելք, հարավ և արևմուտք:

Մուտքային օրինակները այնպիսին են, որ միշտ հնարավոր է (i₁, j₁)-ից հասնել (i₂, j₂) վանդակը:

Ելք

Ելքային ֆայլը պարունակում է մեկ ամբողջ թիվ՝ (i₁, j₁)-ից (i₂, j₂) վանդակը հասնելու համար անհրաժեշտ մինիմալ քայլերի քանակը:

Օրինակ

Մուտք.
4 2
1 1 4 1
E SW
x EW
NW ES
N x

Ելք.
5

Մուտքային խաղատախտակի տեսքը.
 
 
Օրինակում օգտագործվում են հետևյալ քայլերը.
Պտտել (2,2)-ը ժամսլաքի ուղղությամբ: Տեղափոխվել (1,2) վանդակը:
Պտտել (3,2)-ը ժամսլաքի հակառակ ուղղությամբ: Տեղափոխվել (2,2) վանդակը:
Պտտել (3,2)-ը ժամսլաքի հակառակ ուղղությամբ: Տեղափոխվել (3,2) վանդակը:
Պտտել (3,1)-ը ժամսլաքի ուղղությամբ: Տեղափոխվել (3,1) վանդակը:
Պտտել (3,1)-ը ժամսլաքի ուղղությամբ: Տեղափոխվել (4,1) վանդակը: