Reconstruir imagen


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Python 35.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Se ha recibido una imagen captada por el satélite IslaSat. El satélite captura la imagen de un área rectangular. Para representar la imagen se divide el área rectangular de dimensiones M x N en M x N celdas como se muestra en la siguiente figura. El satélite es monocromático y solo detecta dos colores. Dependiendo de la saturación del color en cada celda, el satélite asume que una celda es negra o blanca.

Descripcion

Lo que se obtiene es una imagen deformada y debe ser reconstruida. La reconstrucción de la imagen consiste en trazar un contorno de perímetro mínimo de forma tal que todos los puntos negros queden incluidos. El contorno se traza sobre las aristas de la celda, como se muestra en la figura de abajo.

Descripcion

Tarea

Hacer un programa que permita:

  • Leer desde el fichero de entrada las dimensiones del área rectangular y las coordenadas de las celdas asumidas como negras.
  • Determinar el contorno de perímetro mínimo.
  • Escribir hacia la salida el valor del perímetro mínimo de la imagen reconstruida.

Entrada

La entrada contiene:

Línea 1: M, N, cantidad de filas y columnas del tablero.

Línea 2..M+1: En cada fila aparecerán N dígitos 0 y 1, donde 1 representan los puntos negros.

Salida

La salida contiene en una sola línea el valor de la longitud del perímetro de la imagen reconstruida.

Restricciones

  • 1 \le M,N \le 10,000

Ejemplo de Entrada

5 11
00000010010
01001001000
10000010001
00101001100
00101010000

Ejemplo de Salida

32

Comments


  • 0
    Maite  commented on Dec. 20, 2022, 3:33 p.m.

    xq se me va de tiempo si uso dos ciclos for anidados q seria O(n*m) q es 10^8?


    • 2
      Marco_Escandon  commented on Dec. 22, 2022, 4:01 p.m.

      Agrega esto dentro del main para optimizar la entrada en el que te da 8 casos de prueba: ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);


    • 3
      josed  commented on Dec. 21, 2022, 3:34 p.m.

      La entrada puede ser un poco grande, intenta optimizar la lectura.