Shades
Зимни Състезания по Информатика, 2014
Time Limit: 0.2s, Memory Limit: 64MiB
Преди много години един египетски владетел имал следния проблем. През лятото неговите поданици негодували, че в града няма достатъчно сянка, а през зимата - че няма достатъчно слънце. За да покаже колко неоправдани са оплакванията им, владетелят предложил шепа златни монети на всеки от тях, който дойде от къщата си до имението му, като през точно половината време е на сянка, а през останалото - на слънце. Единственият човек, който успял да спечели наградата, намерил път изцяло на слънце, но носел шапка през половината време.

Това накратко е историята в напоследък нашумялата книга "Fifty% Shades of Gray", която Ели, разбира се, не пропусна да прочете. Сега тя се чуди дали задачата може да бъде решена без измамата с шапката.

За простота тя представя града като грид с N реда и M колони, като най-горната лява клетка е с ред 1 и колона 1, а най-долната дясна – с ред N и колона M. Всяка клетка е или черна (сенчеста) или бяла (на слънце). Ели не знае къде точно се е намирало имението на владетеля, както и различните къщи, от които са идвали хората, затова тя иска по-генерално решение, което отговаря на въпроси от типа "намери път с равен брой бели и черни полета от клетката в ред SR и колона SC до тази в ред ER и колона EC". От една клетка човек може да се премести в някоя от четирите съседни (стига да не излиза от грида).

Сега момичето е дало задачата на вас. Е, наградата не е шепа златни монети, но все пак си заслужава. Затова вие решавате да напишете програма shades, която се справя с този проблем.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, M - съответно броят редове и броят колони. Следват N реда, всеки съдържащ стринг с дължина M, съставен от символите 'B' и 'W', обозначаващи, съответно, черна и бяла клетка. След описанието на града на нов ред ще стои цялото число Q – броя въпроси, които вашата програма трябва да обработи. Следващите Q реда съдържат по четири цели числа SRi SCi ERi ECi, задаващи началната и крайната клетка за съответния въпрос. Възможно е началната и крайната клетка да са с еднакви координати.
Изход
За всеки въпрос изведете на един единствен ред едно цяло число – колко клетки посещава намерения от вас път, последвано от самия път - стринг с един по-малко символ от зададеното число. Пътят трябва да бъде представен като последователност от символи 'U', 'R', 'D', 'L', указващи, съответно, движение нагоре (намаляващ ред), надясно (нарастваща колона), надолу (нарастващ ред) и наляво (намаляваща колона). Разрешено е минаването през всяка от клетките (включително началната и крайната) по повече от веднъж. Не е задължително изведеният от вас път да е с минимална дължина. Все пак, изпечатаният от вас път не трябва да надвишава 1,000,000 символа за всеки от въпросите. Ако такъв път няма, вместо това изведете ред с числото -1.
Ограничения
  • 1 ≤ Q ≤ 10
  • 1 ≤ N, M ≤ 500
  • 1 ≤ SRi ERiN
  • 1 ≤ SCi ECiM
Примерен Вход Примерен Изход
5 6 BWWBWB BBBWBB WBBBBW WWBBWW BBWWBB 4 1 1 5 6 4 5 2 1 5 1 5 2 3 4 4 4 10 RRDRDRRDD -1 6 RRRLL 8 URRDDLL
Мрън!