N реда и м стълба. Всяка една клетка представлява шатра на амбулантен търговец, която е означена с някоя от главните латински букви



Дата01.08.2018
Размер34.19 Kb.
SMS

Лятото свърши и всички се прибраха от морето. Гората отново е пренаселена! Големият брой животни естествено привлече множество търговци, които запълниха горската поляна. Продавачите на дребни стоки като бурканчета мед и пчелни пити са буквално навсякъде! Мечо Пух започна да преглежда офертите за пчелния мед от новата реколта, с който да попълни понамалелите си запаси от миналата зима, и реши да провери промоциите на амбулантните търговци. Той отиде до най-близката спирка на горското метро и бързо се озова на новоформиралия се пазар. С пристигането си Пух започна да разглежда множеството сергии и беше много щастлив... имаше толкова много мед! Опиянен от гледката на пълните бурканчета, Пух се луташе напред-назад, наляво-надясно, докато изведнъж с ужас установи, че се е изгубил. Нищо наоколо не му изглеждаше познато. С успокоение напипа GSM апарата в джоба си и веднага се обади на Бухал за помощ.

Горската поляна може да бъде представена като правоъгълна таблица с N реда и М стълба. Всяка една клетка представлява шатра на амбулантен търговец, която е означена с някоя от главните латински букви, или пчелен кошер, означен със знака ‘#’, в който Мечо няма никакво желание да стъпва, поради стари вражди с пчелите. Пух може да преминава от една клетка в друга, при условие че двете клетки споделят обща страна и нито една от двете клетки не е пчелен кошер. Благодарение на доброто покритие на мрежата на Горския Мобилен Оператор (ГМО) Бухал може да определи с голяма точност местоположението на Мечо Пух върху горската поляна – реда R и колоната C в правоъгълната таблица, където той се намира. За съжаление тарифният план от ГМО на Бухал не е много изгоден. Мобилните разговорите са невъобразимо скъпи, а включените безплатни минути са малко и, разбира се, винаги са свършили, когато му потрябват. Положението със SMS-ите е почти същото. Кратките текстови съобщения се таксуват не на бройка, а на брой символи в тях. Именно за това Бухал иска да изпрати SMS на Мечо с минимална дължина, съдържащ дума, която описва път, който ще го изведе до някой от ръбовете на горската поляна, откъдето Пух отново ще хване горското метро и благополучно ще се прибере у дома. Буквите от думата от SMS-а показват през кои шатри трябва да мине Мечо, за да излезе от поляната. Ако Пух е стигнал до последната буква от думата и все още не е стигнал до ръб на поляната, той продължава от текущото си положение с първата буква от същата дума. Тези действия се повтарят, докато Мечо не излезе от поляната.

Бухал би се забавил прекалено дълго с намирането на подходящ път, затова той ви моли да му помогнете като напишете програма, която го намира вместо него.

На първия ред от входния файл sms.in ще стоят числата N и M – съответно броят редове и броят колони на правоъгълната таблица, описваща горската поляна. На втория ред са числата R и Cредът и колоната, в които се намира Мечо Пух. На всеки от следващите N реда от входния файл са записани по M символа (без интервали помежду им), даващи информацията за съответните клетки от горската поляна. (Заб.: номерирането на редовете и колоните от правоъгълната таблица започва от 0).

В изходния файл sms.out на първия ред запишете числото P – броят клетки, през които трябва да мине Мечо Пух. На i+1ред от изходния файл изведете i-тата клетка от пътя на Мечо Пух.




sms.in

sms.out

6 7

2 4


##PZ#OP

NABABCD


QBEFAB#

ZAFABCQ


YBAC#AB

N#BDYYC


10

2 4


1 4

1 3


1 2

1 1


2 1

3 1


4 1

4 2


5 2

Обяснение: Този път от десет клетки може да бъде описан с думата „AB”. Друг път за изход може да бъде описан с думата „ABC”, но дължината на SMS-а ще бъде по-голяма.




sms.in

sms.out

10 9

7 4


MUSALAW#P

POOH#EERC

TLEINNI#M

YNWHNIEWA

ZAEINNIHG

#FMIIXJ#A

#N##HOT#Z

BAN#WEB#I

NNPM###ON

HONEY###E



22

7 4


6 4

5 4


4 4

3 4


3 5

3 6


3 7

4 7


4 6

4 5


Продължение:

4 4


4 3

4 2


3 2

3 3


2 3

2 4


2 5

2 6


1 6

0 6


Обяснение: Този път от 22 клетки може да бъде описан с думата „WHINNIE”. Не е задължително дължината на пътя да е кратен на дължината на думата и не е забранено в една клетка да се влиза повече от веднъж.



Ограничения:

5 <= N, M <= 256



Оценяване:

При некоректен изход или при изход, съдържащ път с повече от 3 * N * M клетки, за съответния тест получавате 0 точки. В противен случай, резултатът от теста ще е дължината на най-късата дума, с която може да се опише изведения път. На базата на тези резултати ще се извърши релативно оценяване.


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница