DMPG '15 G1 - Marcia and Maze - Olympiads Online Judge

DMPG '15 G1 - Marcia and Maze

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 0.6s

Memory limit: 256M

Author:

FatalEagle

Problem types

For your birthday, you have received Marcia the android and an $N \times N$ ~N \times N~ square grid maze. Once turned on, Marcia repeats this sequence of moves indefinitely: move $X$ ~X~ $(0 \le X < N)$ ~(0 \le X < N)~ squares forward, then turn $90^{\circ}$ ~90^{\circ}~ right. Marcia has human-like emotions, so you don't want to crash her into the maze's walls, and neither do you want her to move out of the maze. What is the largest possible $X$ ~X~ such that there is a valid starting square to place Marcia on so that when you turn it on, it will never crash into walls or move out of the maze?

Input Specification

The first line of input will contain the integer $N$ ~N~.
The next $N$ ~N~ lines each contain $N$ ~N~ characters that describe the maze. . indicates a free space and # indicates a wall. There will be at least one empty space in the maze.

Constraints

Subtask 1 [30%]

$1 \le N \le 20$ ~1 \le N \le 20~

Subtask 2 [30%]

$1 \le N \le 100$ ~1 \le N \le 100~

Subtask 3 [40%]

$1 \le N \le 500$ ~1 \le N \le 500~

Output Specification

Output the largest $X$ ~X~ required by the problem statement.

Sample Input

5
.....
#.##.
.....
.#.#.
#....

Sample Output

Explanation of Output for Sample Input

You can place Marcia at the bottom right corner.

Comments

-7

TheATeam commented on March 7, 2016, 5:44 p.m.

I've tried everything I could to speed this up but its still too slow and I noticed no one has done it in Python. Is it impossible?

This comment is hidden due to too much negative feedback. Show it anyway.

8

bobhob314 commented on March 7, 2016, 6:09 p.m. ← edit 4 →

Your code, when submitted in PyPy, still TLEs. It's not guaranteed that Python can be used to solve all problems, and in any case it seems to be an issue with your solution, as a successful Python submission has been made. If you need any more help, leave a reply.

-6

TheATeam commented on March 7, 2016, 6:30 p.m. ← edit 3 →

Nvm d did it somehow. Any hints?

This comment is hidden due to too much negative feedback. Show it anyway.

13

d commented on March 8, 2016, 4:10 a.m.

$\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~ preprocessing will allow you to determine, in constant time, whether an arbitrary horizontal/vertical line segment contains a #.