11501 - Laurel Creek

[redroof]

A clarification question -- Can we pick up the log (length == 1) in the figure below? (suppose we stand on 'B')

Code: Select all

....
.B.S
.|..
...E

If yes, we have a path to traverse from B to E, otherwise not. thanks.

[baodog]

Yes, you can.

[redroof]

Got AC. Actually we don't need to consider the above case. My ac code assumes all logs are connected by two stumps.

[Vytenis]

Is there some simple solution to this problem? I thought that a kind of BFS is needed, but it seemed that the potential state space is too big for it to run in time.

[redroof]

I use BFS. Considering the available slots where the log can be picked up or put down, the state space is not that big. Because there are at most 15 stumps with limited row and column size(<= 15) and logs only exist between stumps, the following case is the one that comes with the greatest number of logs. right?

Code: Select all

S-S-S-S
|.|.|.|
S-S-S-S
|.|.|.|
S-S-S-S
|.|.|.|
S-S-S-.

There are less than 24 positions that logs can be put down. Also the current position can be represented with 4 bits (we can only stand on a stump), so the state space can be represented as 4bit + 24bit = 28 bits.

[bemscho]

I use BFS, too. But I got WA at 0.010
I don't consider length or location of logs, but only stumps. Is this wrong approach?
Could you give me some critical test case?

[redroof]

Code: Select all

....S...S..
........|..
B-----S.|.E
......|.|..
......|.S..
......|....
....S-S....

I don't know how you process with only the information of stumps. But try the above case.