## COCI '06 Contest 1 #6 Debug

View as PDF

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

While debugging a program Mirko noticed that a bug in the program may be linked with the existence of so called square killers in the program memory. The program memory is a matrix composed of rows and columns consisting only of zeroes and ones. A square killer is a square submatrix in memory, consisting of more than one character, that, when rotated degrees looks exactly the same. For example, the following matrix contains 3 square killers:

 101010 111001 101001 ....10 ....01 ...... ...... ...00. ...00. 101... 111... 101... memory killer killer killer

Mirko is wondering if there is a connection between the size of the largest square killer and the bug in the program. Help Mirko by writing a program that, given the layout of the memory, outputs the size of the largest square killer. The size of the square killer is the number of rows (or columns) that the killer consists of. In the example above the killer sizes are , and , respectively.

#### Input Specification

The first will contain two integers, and , smaller than or equal to . The next lines will each contain characters (0 or 1) with no spaces.

#### Output Specification

Output the size of the largest killer on a single line, or output -1 if there are no square killers.

#### Sample Input 1

3 6
101010
111001
101001

#### Sample Output 1

3

#### Sample Input 2

4 5
10010
01010
10101
01001

#### Sample Output 2

3

#### Sample Input 3

3 3
101
111
100

#### Sample Output 3

-1

## Comments

• commented on May 22, 2017, 10:54 a.m. edited

uhh I think a 1 second time limit is way too restrictive for python. can someone pls increase

EDIT: Sample data #3 is incorrect there is a square killer with side length 2 which is ['01','11']

• commented on Nov. 6, 2016, 5:59 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.