Reconstruir imagen

Points: 100 (partial)

Time limit: 2.0s

Python 35.0s

Memory limit: 128M

Author:

FrankHG

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$ ~M x N~ en $M x N$ ~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.

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.

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$ ~M, N~, cantidad de filas y columnas del tablero.

Línea 2..M+1: En cada fila aparecerán $N$ ~N~ dígitos $0$ ~0~ y $1$ ~1~, donde $1$ ~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$ ~1 \le M,N \le 10,000~

Ejemplo de Entrada

5 11
00000010010
01001001000
10000010001
00101001100
00101010000

Ejemplo de Salida

Comments

1

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?

3

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.