III Copa UHEnded |
Fito trabaja en el zoológico nacional y es el encargado de organizar los recorridos guiados que se ofrecen a los visitantes. El zoológico está dividido en varias áreas. Un recorrido consiste en un camino que sale de un área dada, visita otras y termina en el área desde la cual partió, sin estar obligado a que todas las áreas visitadas sean diferentes.Todas las áreas son tan grandes que es posible tener un recorrido que solo la contemple a ella. En tal caso se considera que el recorrido sale de esa área y termina en ella misma, usando un solo viaje. El objetivo que Fito persigue es que para toda área existe al menos un recorrido que parta de ella. Para esto tiene el mapa del zoológico y algunos viajes que ya se están haciendo y lo que quiere es añadir la menor cantidad de viajes nuevos que garantice se cumpla lo que desea.
La entrada consiste de $N$ líneas, $2 \leq N \leq 20$. Cada línea contiene una cadena de longitud $N$. Los caracteres de cada línea son $“0”$ o $“1”$. La letra $j-ésima$ de la línea $i$ es “1” si y solo si hay un viaje desde el área $i$ al área $j$. Los viajes que unen unas áreas con otras no son necesariamente simétricos.
La salida es un número entero que representa la menor cantidad de viajes que hay que añadir para que todas las áreas tengan al menos un recorrido que parta de ella.