An Animal Contest 2 P3 - Koala Balloons

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.75s
Java 2.5s
Python 3.0s
Memory limit: 512M

Problem type

To further celebrate his birthday, Sanjay is at Koala Land with his best friend, Sam. While Sam is on a scary looking roller coaster that Sanjay didn't want to go on, Sanjay decides to buy him balloons!

Imagine Koala Land as an N by M grid. The balloon store is situated at the top left cell, (1, 1), and Sam will leave the roller coaster at the bottom right cell with coordinates (N, M). Scattered throughout the grid are amusement rides that serve as obstacles.

Sanjay wants to bring Sam as many balloons as possible, but is limited by the presence of the obstacles. A package of x balloons takes up a square space of x by x. Balloons, as solid objects, can only move through spaces that are not occupied by obstacles. In other words, if Sanjay takes x balloons, he can only move through spaces of minimum size x by x. At any cell, Sanjay is allowed to move up, down, left, or right, as long as the resulting cell is contained in the dimensions of the grid. Given this constraint, what's the maximum number of balloons that Sanjay can bring Sam?

Note that if Sanjay starts with x balloons, he will initially occupy the square defined by the coordinates (1, 1), (x, 1), (x, x), and (1, x). Only the bottom right corner of Sanjay's group of balloons must reach (N, M) for him to reach Sam. Additionally, cells (1, 1) and (N, M) will never be blocked.

For this problem, Python users are recommended to use PYPY over CPython.


For all subtasks:

2 \le N, M \le 1500

Subtask 1 [20%]

2 \le N, M \le 200

Subtask 2 [80%]

No additional constraints.

Input Specification

The input will contain N lines of M characters, representing the grid as described in the statement.

An obstacle is represented by X and an empty space is represented by O.

Output Specification

Output the maximum number of balloons that Sanjay can bring Sam.

If Sanjay cannot bring Sam any balloons, output 0.

Sample Input 1

4 4

Sample Output 1


Explanation for Sample 1

If Sanjay takes two balloons, he initially occupies the square defined by the coordinates, (1, 1), (2, 1), (2, 2), and (1, 2). If he moves right, down, down, and finally right, he can reach his destination.

Sample Input 2

4 5

Sample Output 2



There are no comments at the moment.