Manchas en el Papel

Submit solution
Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M
Author:
antonio_bouza
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Swift, VB

Se derramó algo de tinta sobre un papel cuadriculado que medía \(M × N\) celdas. Cada celda del papel ahora se considera pintada o limpia. Dos celdas pintadas pertenecen a la misma mancha si hay un camino de una de las celdas a la otra que atraviesa solo celdas pintadas y en cada paso se mueve de una celda a otra solo horizontal o verticalmente.

Cuente el número de manchas y el área de la mancha más grande (es decir, la cantidad de celdas que la componen).

Entrada

La primera línea de entrada contiene los números enteros M y N \((1 \leq M, N \leq 10^5, 1 < M×N \leq 10^6)\). Cada una de las siguientes M líneas consta de N caracteres 0 o 1, donde 0 denota una celda limpia y 1 una celda pintada. Hay al menos una celda pintada.

Salida

La única línea de salida debe contener dos números enteros: el número de manchas y el área de la mancha más grande.

Ejemplo de Entrada

6 7
1001001
1111011
1001000
1001111
0100000
0000000

Ejemplo de Salida

3 13

Comments


  • 1
    LeandroGamer  commented on Nov. 21, 2023, 9:07 p.m.

    Cual es el mayor valor de M y de N.


    • 1
      eblabrada  commented on Nov. 25, 2023, 1:30 p.m.

      Te aseguran que 1 < M \times N \le 10^6.