In the universe, there exists a magical land full of nerds called DMOJistan. The Nerds of DMOJistan are massive fans of the game "Genshin Impact". Nerds specifically enjoy playing with one character: Hu-Tao. Nerds enjoy playing Hu-Tao so much, that in the name of Hu-Tao, the Nerds decided to create a fractal in her name: the so-called Hu-Tao Fractal.
"A fractal is defined as a never-ending pattern, which continually repeats itself"
The smallest Hu-Tao Fractal looks like the pattern below.
1 1 1
1 0 1
1 1 1
A bigger Hu-Tao Fractal would be 3 times larger, and where there is currently a 1
in the base fractal, that section will have a copy of a Hu-Tao Fractal that's 1/3rd the size of the one we're trying to make. The spot that has a 0
will be filled with 0
's.
Therefore, the next Hu-Tao Fractal would look like the following:
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1
1 0 1 0 0 0 1 0 1
1 1 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
This pattern can of course continue repeating forever, and ever. But the fractal will always be of a size that is a power of ().
Now we can also look for a Hu-Tao Fractal the other way around. First we can look for an area which has a width that is equal to a power of 3. Then we can divide that area into 9 sections, with 3 cuts to each side. All of the areas on the outside should be valid Hu-Tao Fractals, and should repeat themselves at ever smaller scales until the next fractal would be of size 0
. The section at the center should be filled with 0
's.
Now let's look at a valid Hu-Tao Fractal:
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1
1 0 1 0 0 0 1 0 1
1 1 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
This area has a side length of 9
, which is a power of three.
Now let's divide it up.
1 1 1 | 1 1 1 | 1 1 1
1 0 1 | 1 0 1 | 1 0 1
1 1 1 | 1 1 1 | 1 1 1
------+-------+------
1 1 1 | 0 0 0 | 1 1 1
1 0 1 | 0 0 0 | 1 0 1
1 1 1 | 0 0 0 | 1 1 1
------+-------+------
1 1 1 | 1 1 1 | 1 1 1
1 0 1 | 1 0 1 | 1 0 1
1 1 1 | 1 1 1 | 1 1 1
All the sections on the sides look like this;
1 1 1
1 0 1
1 1 1
Which is the smallest Hu-Tao Fractal which is possible. That means that the sections on the outside are good.
Now let's look at the section in the center;
0 0 0
0 0 0
0 0 0
It's all zeros! Which means that this is a valid Hu-Tao Fractal that is 9
units wide!
Knowing this, the Nerds wonder about the following problem:
"Given , an by square grid with all being either 0 or 1, what is the size of the greatest Hu-Tao Fractal that we can identify?"
Being a nerd yourself, you decide to help them in solving the problem.
Constraints
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [60%]
No additional constraints.
Input Specification
The first line will contain one integer, , the length and width of the square grid.
The next lines will contain space-seperated integers, consisting of only 0's and 1's.
Output Specification
Output one integer, the side length of the largest identifiable Hu-Tao Fractal.
Sample Input 1
3
1 1 1
1 0 1
1 1 1
Sample Output 1
3
Sample Input 2
9
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1
1 0 1 0 0 0 1 0 1
1 1 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
Sample Output 2
9
Sample Input 3
4
1 1 1 1
1 0 1 1
1 1 1 1
1 1 1 1
Sample Output 3
3
Sample Input 4
3
0 0 0
0 0 1
0 0 0
Sample Output 4
0
Comments