DMPG '15 G1 - Marcia and Maze

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem types

For your birthday, you have received Marcia the android and an N \times N square grid maze. Once turned on, Marcia repeats this sequence of moves indefinitely: move X (0 \le X < N) squares forward, then turn 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 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.
The next N lines each contain 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.


Subtask 1 [30%]

1 \le N \le 20

Subtask 2 [30%]

1 \le N \le 100

Subtask 3 [40%]

1 \le N \le 500

Output Specification

Output the largest X required by the problem statement.

Sample Input


Sample Output


Explanation of Output for Sample Input

You can place Marcia at the bottom right corner.


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

    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 2

      Your code, when submitted in PyPy2, 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 2

        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) preprocessing will allow you to determine, in constant time, whether an arbitrary horizontal/vertical line segment contains a #.