## 11501 - Laurel Creek

Moderator: Board moderators

redroof
New poster
Posts: 5
Joined: Sun Sep 28, 2008 12:51 pm

### 11501 - Laurel Creek

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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### Re: 11501 - Laurel Creek

Yes, you can.

redroof
New poster
Posts: 5
Joined: Sun Sep 28, 2008 12:51 pm

### Re: 11501 - Laurel Creek

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

Vytenis
New poster
Posts: 7
Joined: Mon Aug 04, 2008 8:16 pm

### Re: 11501 - Laurel Creek

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
New poster
Posts: 5
Joined: Sun Sep 28, 2008 12:51 pm

### Re: 11501 - Laurel Creek

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
New poster
Posts: 1
Joined: Thu Oct 09, 2008 7:57 pm

### Re: 11501 - Laurel Creek

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
New poster
Posts: 5
Joined: Sun Sep 28, 2008 12:51 pm

### Re: 11501 - Laurel Creek

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.