1

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.

2

Re: The Little Red Riding Hood and Grey Wolf

Hello, olimp_20, you wrote: _> 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. We take the graph in whom to each peak it is attributed 3 coordinates. 2 from them - square coordinates, one more - step number. Also we use . To build all graph it is not necessary, enough to be able to sort out proceeding edges from the given peak. The third coordinate always changes t-> t+1. We stop in type peak (N, M, x).

3

Re: The Little Red Riding Hood and Grey Wolf

Hello, olimp_20, you wrote: whether _> be valid  can such intellectual in this task? Is obliged to be. For example, if the Wolf starts from (1,3) and moves on route L, D, D, D, D..., U, U, U..., D, D... (Runs on 2 column upwards-downwards) the Cap should descend somewhere reversely upwards.

4

Re: The Little Red Riding Hood and Grey Wolf

Hello, samius, you wrote: S> we Take the graph in whom to each peak it is attributed 3 coordinates. 2 from them - square coordinates, one more - step number. Also we use . To build all graph it is not necessary, enough to be able to sort out proceeding edges from the given peak. The third coordinate always changes t-> t+1. We stop in type peak (N, M, x). If I correctly understood,  - width-first search. Each new wave at width moves to seek time to the yet not visited peaks of the graph. If  it is necessary to depart, the cycle turns out. There is a question: how in time to quit a cycle,  to continue driving? And how to search for correctly direction if it is necessary to go through already visited peaks?

5

Re: The Little Red Riding Hood and Grey Wolf

Hello, Lexey, you wrote: L> Hello, olimp_20, you wrote: whether _>> be valid  can such intellectual in this task? L> is obliged to be. For example, if the Wolf starts from (1,3) and moves on route L, D, D, D, D..., U, U, U..., D, D... (Runs on 2 column upwards-downwards) the Cap should descend somewhere reversely upwards. We note that if the width and is long woods more than 2  it is enough no more than one "a step back".

6

Re: The Little Red Riding Hood and Grey Wolf

Hello, olimp_20, you wrote: _> If I correctly understood,  - width-first search. _> each new wave at width moves to seek time to the yet not visited peaks of the graph. If  it is necessary to depart, the cycle turns out. There is a question: how in time to quit a cycle,  to continue driving? And how to search for correctly direction if it is necessary to go through already visited peaks? Only 2 from 3 peak coordinates can have repetition. And coordinate-number of a step each time the new. So, the cycle is eliminated. To search for a direction it is not necessary,  all  to within equivalent on number of steps of ways.

7

Re: The Little Red Riding Hood and Grey Wolf

Hello, Kodt, you wrote: As the Hat on everyone to a course leaves from current position... The modeling Step consists that the cell becomes "true" in only case when when - it is not marked on a card as # - in it is not present on the previous step and there will be no on leaking a wolf - in one of adjacent (adjacent) cells of the previous step there was "true" 0 1 1 1 0x0 0x0 0x2 4x2 0 0 3 3 "" - current position of the Hat, 1,2,3,4 - a step on which the position has been visited. Where exactly the Hat in the cellular automatic machine leaves? In "width-first search" the new course is fulfilled in not visited positions, and in the cellular automatic machine at each stage all admissible positions as though become again not visited? That is a question: how to supervise Hat driving that she "did not forget" to move to the grandmother (on finish)?

8

Re: The Little Red Riding Hood and Grey Wolf

9

Re: The Little Red Riding Hood and Grey Wolf

Hello, Chorkov, you wrote: L>> Is obliged to be. For example, if the Wolf starts from (1,3) and moves on route L, D, D, D, D..., U, U, U..., D, D... (Runs on 2 column upwards-downwards) the Cap should descend somewhere reversely upwards. A C> we Note that if the width and is long woods more than 2  it is enough no more than one "a step back". For example, the grandmother lives among dense "building" of trees, and its wolf of 31999 courses protects, without allowing to transit. And the Cap it is necessary many and to walk long before to visit the grandmother. It will walk forward-back, or to the right-to the left, either on a circle, or on the eight is its business. But "steps back" it should make much.))