OJ Board

I thought the solution to this problem involved finding the worst of the least weight (fewest roses stepped on) paths starting from the four squares around the plinth ('P') square. Apparently this is not the case. My attempt at solution went something like this:

1) Find least destructive path from square above plinth to any edge square.
2) Find least destructive path from square right of plinth to any edge square.
3) Find least destructive path from square below plinth to any edge square.
4) Find least destructive path from square left of plinth to any edge square.

Take the worst of the above and that is the most roses that will get trampled. However, I get wrong answer with that approach, so clearly there is more to the problem than this. Can someone who got an accepted status or the problem author comment, please.

Mike

I have not tried this problem yet, but it seems like an A* search problem..

I haven't solved the problem yet, but I am sure I understood it.
The problem asks you to find a path such that the number of trampled roses is minimum, where you take the maximum of the 4 possible "rotations" of that path. Your approach does not solve this (although I can't give you a counterexample right now).
So, naive solution would be:
- Loop over all possible paths
- evaluate number of trampled roses for each direction
- let cost of that path be maximum of trampled roses for a direction
- select path with minimum cost.

Mike, here is a counter-example to your solution:
Your approach would return that no roses will be trampled because there is a path from all four neighbours of the center to the edge so that no roses are trampled. However, the four paths are not all rotations of each other. So, the gardener will not have a strategy such that no roses are trampled regardless of which direction s/he is facing.

Igor

So, if I understand this correctly. You have to try all minimal exit paths, on all four rotations of the field and print the worst case scenario?

Mike

I don't quite understand the problem...
What's the purpose of 'P' in the input?
And why I have to tramples 2 roses to escape for the sample?

I haven't solved the problem, but I can tell you that your hands are tied and eyes covered. so there must be a generic strategy that will reduce the number of flowers trampled.

Cho wrote:I don't quite understand the problem...
What's the purpose of 'P' in the input?
And why I have to tramples 2 roses to escape for the sample?

P has no significance. It is always in the middle square of the map.

Since you don't know your direction, you can never be certain that your first step is neither north nor south, and it should be obvious that any path starting with north or south needs to cross at least two roses. Hence there is no way to guarantee that fewer than 2 roses are trampled.

Then I think I really misunderstand the problem. The problem states that "You must come up with an escape path that tramples the fewest possible roses". I thought the gardener (me) can make decision when I am escaping. So for the following input: Originally, I think the answer is 2 because if I'm unlucky and walking towards south, I will immediately know that there will be three more roses in front of me. So I should turn back and escape in opposite direction. Two roses are trampled as result.

But after reading the posts, it seems that the answer should be 4. Can someone confirm that?

Cho wrote:Then I think I really misunderstand the problem. The problem states that "You must come up with an escape path that tramples the fewest possible roses". I thought the gardener (me) can make decision when I am escaping. So for the following input:

Code: Select all

<snip>

Originally, I think the answer is 2 because if I'm unlucky and walking towards south, I will immediately know that there will be three more roses in front of me. So I should turn back and escape in opposite direction. Two roses are trampled as result.

Yes, you can make choices, but you never learn which direction you're facing, even after taking a few steps. So in your example if you take a step south you won't know that there are three more roses in front of you, since you have no way of knowing that you happened to take a step south (it might as well have been east, west or north for all you know).

I guess a slightly more realistic version of the problem would be that the gardener can sense when he tramples a rose, and hence conclude that some directions are impossible.

But after reading the posts, it seems that the answer should be 4. Can someone confirm that?

Yup, that's correct.

Hmm. Cho brings up an interesting point and for his example an escape with trampling 3 roses is possible and consistent with the problem description:

Start by taking two steps forward, in the yet unknown direction.
If you step on a rose with your second step, then you know (since you memorised the map) that you are either walking south or east, in which case you turn around and keep walking in the opposite direction, thereby trampling one more rose, for a total of three.
If you didn't step on a rose with your second step, you know you are either walking north or west, in which case you can escape by continueing walking in the same direction without stepping on an other rose.

To get the intended answer (4) in this case, you either should not be aware that you step on a rose (unlikely) or be forced to determine your path before you start walking. The latter could be meant by the phrase "You must come up with an escape path...".

Actually, I think BFS is fine, since the number of states isn't that big..

Is it true then that the solution to the problem is:

1) Take all possible minimum weight (least roses trampled) exit paths, since we don't know the choice of optimal route that the farmer will make and he can choose any optimal route, since they all have equal weight.
2) Apply them to all four possible rotations of the board, adjusting the maximum number of roses trampled, accordingly, since the farmer can attempt any optimal route, without caring which direction he is actually facing. The final maximum number of roses trampled is the answer.

Mike

No.

Consider, for example, the test case There is only one minimum weight exit path, but applying your second step to that path would give you the answer "4", whereas the real answer is "2" (take two steps forward, then walk left)

I am confused with the test case you gave here per.

Here I am giving what happens in the four direction:

North: No obstacle. 0
South: steps and break 1. if he continues in this path he will break more. So he gets back. And go to north. So in this case 1.
Same for east and west.

So answer must be 1. why two?

Well here is a case:
00R00
R00RR
R0P0R
00000
00000

I know the man does not know which direction he is. So consider walking to north. He steps in safe place. Then if he again goes to north he will break 1. but if he follows left then north he will be able to go out without breaking. Right? But how will he select whether he will go to left or straight? At least he does not know the direction.

I guess the total answer is 0 for this case. But actually what the problem said? AT MOST right? So here for my case if he continues to north he have to break one to go out. Again if he steps north then two right then he breaks two. That means at most he breaks 2 to go out from the field? Hoof, I am puzzled! Can anybody explain what actually happens for my and per