Topic: The Little Red Riding Hood and Grey Wolf
Time limit 1. The Little Red Riding Hood hastens to visit the sick grandmother and to carry to it medicines and meal. Its way lies through dense wood which is broken into squares. From a square it is possible to get to a square only moving upwards, downwards, to the left or to the right. For wood limits it is impossible to quit, wood is surrounded by an impassable bog. Wood has the rectangle form in which N lines and M columns. The Little Red Riding Hood lives in left upper to a corner of this wood, and its grandmother - in the right lower. The house of the grandmother is protected by hunters. That wood the Grey Wolf whom very much it is necessary to be careful to the Little Red Riding Hood wanders. Fortunately, the home position and its route to it are known. For what least amount of steps the Little Red Riding Hood can achieve the object, observing at driving such rules (the step is a relocation from a cell in an adjacent cell): 1. It is possible to move only in adjacent across or verticals the free cell. 2. Relocation is carried out in turn: at first the Grey Wolf, then the Little Red Riding Hood. 3. Finding in one square of the Little Red Riding Hood and the Grey Wolf is not admitted. 4. Courses of the Little Red Riding Hood and the Grey Wolf are mandatory. 5. If courses of the Grey Wolf ended, it remains in the last reached cell. But it is in advance known that it thus does not block a way of the Little Red Riding Hood to the grandmother. If the Grey Wolf reached finish (a square in which there lives the grandmother) he is killed by hunters. The input data In the first line field size: two numbers through a gap 0 <N, M<=150. Further goes N lines in each of which on M the characters describing a field: a point (.) - The cell is free. A grid (#) - an impassable cell. Next line two numbers - row number and a column where initially there is a Grey Wolf. Further there is a line with the description of a way of the Grey Wolf: R - driving to the right, L - to the left, U - upwards, D - downwards. An amount of courses of the contender no more than 32000. The initial data Singular - the minimum number of steps necessary for achievement of finish. 3 5..... .#... ...#. 1 2 RRLDRRD the answer: 8 As it is represented - here it is possible to use wave algorithm (bypass at width) Truth arises disturbing sensation that to a statement of the problem there can correspond a situation: sees that faces with , recedes on some steps, passing a wolf, and then moves further. Whether be valid can such intellectual in this task? If yes, in what modification of wave algorithm consists? Or here absolutely other approach is necessary? Program performance - 1.