You are not logged in. Please login at www.codechef.com to post your questions!

×

HARD

# EXPLANATION

The challenge here is to simulate Chef's potential escape from the maze within the time constraint. For each time index from 0 until Chef faints from hunger, we calculate every position in the maze Chef could safely occupy. To advance from one time index until the next, for every safe square in the current time step, we mark all of its neighbors as safe in the next step, then mark squares that contain ghosts as unsafe, then move the ghosts, and mark their new locations as unsafe as well. Without optimizations, this approach will time out.

The key is to use bitsets to store the safe positions. Suppose we use one bitset per row of the maze. Then to simulate a north or south move, we need only apply a bitwise "or" between two rows. To simulate an east or west move, we shift the bitmask right or left. The walls of the maze can also be stored as a bitset, and a bitwise "and" operation is used to make sure Chef doesn't try to pass through a wall. Thus it only takes O(M+C) to simulate one time step, instead of O(M * N+C).

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 23 Nov '12, 14:04

0★admin ♦♦
19.8k350498541
accept rate: 36%

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,359
×7
×1

question asked: 23 Nov '12, 14:04

question was seen: 981 times

last updated: 23 Nov '12, 14:04