[CCC] 2002 S3 Blindfold

[SJ]

I was looking over past contests and came across this problem

Quote:

S3J5
Blindfold
Rose and Colin are playing a game in their backyard. Since the backyard is rectangular
we can think of it as a grid with r rows and c columns. Rose and Colin place obstacles on
some of the squares.
The game is played as follows:
Colin covers his eyes with a blindfold then Rose carries him to some grid square in the
backyard. She sets him down so that he is facing north, south, east or west. Colin does
not know this initial position or direction.
Rose then instructs Colin to make a series of m moves through the backyard. Each move
is one of: F - moves forward one grid square in the direction that he is facing,
or
L - turns 90 degrees counter-clockwise, remaining on the same square, or
R - turns 90 degrees clockwise, remaining on the same square.
After making these moves, Colin is standing at some final position. He must now figure
out where he is standing. You will help him by writing a program to determine all
possible final positions. Assume that Colin's initial position, final position, and all
intermediate positions lie within the backyard but never in a square that contains an
obstacle. You may also assume that Colin is always facing a direction that is parallel to
the sides of the backyard (north, south, east, or west).
The input begins with r and c (1 <= r <= 375; 1 <= c <= 80 ), each on a separate line. Next are
r lines of c characters describing the backyard: a period character denotes a grid square
that Colin may walk through; an X character denotes a grid square with an obstacle.
Below the grid is the number m (0 <= m <= 30000) followed by m lines describing Colin's
moves. Each line has a single character: F, L, or R.
Your program should output the backyard grid, indicating all possible final positions with
the * character.
Sample Input (Input file : blind.in)
2
4
....
.XX.
3
F
R
F
Output for Sample Input (Output file : blind.out)
.*..
.XX*

The solution, as shown on the unofficial solution site is pure brute force. ie start from every square, and try the moves list. It passes all the test data, but the data are all small. There can be up to 30000 squares in the map, and up to 30000 moves. Clearly, a brute force solution would time out with a good enough test case. Can anyone suggest a better solution other than brute force?

[A.J]

actually, the brute force solution won't time out at all!

Assuming none of the 30000 squares aren't walls (i.e. worst case), then the time complexity is merely :
O(30000 * 4 * checkingTime)
where checkingTime is how long it takes one to 'check' if the given directions can be followed at every position.

This doesn't time out......and I don't think I can think of any other way other than bruteforce....

[OneOffDriveByPoster]

There are still more than one way to do brute force.

A direct simulation from every starting position and direction is one way.

It is also possible to form a set of offsets from the starting position to all the intermediate positions, the final position and possibly the starting position itself--assuming that we start at "say" (0, 0) and were heading in the direction that would cause Forward to be bring us to "say" (0, 1).

The aforementioned set can let us do better than the straight sim. By definition, a set does not include the same position twice (although the position may indeed be crossed more than once, we only need to check it once).

Try the list for each starting position (or if smart enough, we can keep track of the top-left and bottom-right offsets and trim).

To try other starting directions, you can rotate the grid or the list.

Visualization: Create a transparency with the path laid out; move the transparency over the map and scan to check. Rotating the transparency or the map would achieve about the same effect.

In both the direct sim and the preprocessed offset version there is possibility for giving up early on a starting position. In the preprocessed version, keeping track of "top-left" and "bottom-right" allows some starting positions to be discarded right off the bat.

[A.J]

well, in that case OneOffDriveByPoster, you could also DP at every step and have a 'backtracker' to keep track of the 'moves' (or directions) you followed to reach a certain point, and see if that matches the given set of directions....

at any rate, this is still circling around the same basic bash idea

by "...I don't think I can think of any other way other than bruteforce...." I meant that I don't think there is an elegant way of solving this.

[SJ]

i just tried the worst case i can think of, which requires about 125mill operations. that ran in about 4 seconds - much faster than i thought! I guess brute force would work in time.

the fact that it's a rectangular grid really limits the worst case.

the way i thought of to make it faster is if we store the map as a set a of numbers, then using the bit pattern we can determine whether the current "transparency" fits or not in a pretty small constant time.

anyways, thanks for the replies guys!

[bugzpodder]

think i did the senior version that year.

anyway, one thing to speed it up is to store only all the offsets (corners) to check whether it remains in the maze. Then between two corners is a straight line and you can check whether it contains any obstacles.

[A.J]

yes, and 4 seconds falls under a minure (easily)!

So it works.