|Portada|Blog|Space|

This is the exercise in Spanish: Ejercicio 18 Una isla es una agrupación de celdas (al menos una) con valor 1, cada una de las cuales es adyacente horizontal y/o verticalmente a una celda del mismo grupo. Una isla está delimitada, horizontal y verticalmente, por celdas con valor 0 o por los límites (fronteras) del mapa. Por ejemplo, en el mapa que se presenta en la Figura 3, de tamaño 5x10, hay 6 islas las cuales están compuestas de las siguientes celdas: * Isla 1: (1,1) (1,2) (1,3) (2,1) (2,2) * Isla 2: (3,4) * Isla 3: (4,5) * Isla 4: (5,1) (5,2) (5,3) * Isla 5: (1,6) (1,7) (1,8) (1,9) (1,10) (2,10) (2,7) (3,7) (4,7) (5,7) (5,8) * Isla 6: (5,10) Notar que (3,4) y (4,5) no forman una isla, sino que son dos islas distintas. (a) Escriba el pseudocódigo de un programa que, dado un mapa representado por una matriz de tamaño NxM de ceros y unos, donde 0 representa agua y 1 tierra, imprima las islas encontradas en el mismo. (b) Implemente el programa de la parte anterior en C*. Nota: Se pide que el programa imprima las celdas de cada isla del mapa siguiendo el formato del ejemplo. El orden de impresión entre las islas no es relevante, ni tampoco el orden en que se imprimen las celdas de cada isla. And here we provide a reference implementation: echo $'1110011111\n1100001001\n0001001000\n0000101000\n1110001101' | \ sed 'H;$!d;x;s/\n/%-x/g;s/.//;s/$/%/ :a;s/\(xx*\)\([01]\)\([01]\+%\)/\1\2\1x\3/;ta :b;s/-\([x%y]\)/\1-/g;s/-\([01]\)/y\1-/;tb s/[-%]//g;s/[xy]*0//g;s/1//g;s/x*y*/|<&>/g :c;h;s/\(<x*y*\)>\(.*|.*\)\1y>/\1>\1y>\2/g s/\(<x*y*\)y>\(.*|.*\)\1>/\1y>\1>\2/g s/<\(x*y*>\)\(.*|.*\)<x\1/<\1<x\1\2/g s/<x\(x*y*>\)\(.*|.*\)<\1/<x\1<\1\2/g x;G;/^\(.*\)\n\1$/!{g;bc};x s/||*/-|:/g;:d;s/-|/|x-/g;s/-\([^|-]\)/\1-/g;td s/<\(x*\)/<\1,/g;s/y/x/g :e;s/\([<,|]\)x/\10x/g;s/0x/1/g;s/1x/2/g;s/2x/3/g;s/3x/4/g;s/4x/5/g s/5x/6/g;s/6x/7/g;s/7x/8/g;s/8x/9/g;s/9x/x0/g;te s/<\([^>]*\)>/ (\1)/g;s/-//g;s/|/\nIsla /g;s/.//' Isla 1: (1,1) (2,1) (3,1) (2,2) (1,2) Isla 2: (6,1) (7,1) (7,2) (7,3) (7,4) (7,5) (8,5) (8,1) (9,1) (10,1) (10,2) Isla 3: (4,3) Isla 4: (5,4) Isla 5: (1,5) (2,5) (3,5) Isla 6: (10,5) Explanation: first: Load all lines in memory in the format -x010101%-x11001100%... a: Given two decimal digits, place between them the amount of x+1 that appeared before, eg: xx01 -> xx0xxx1 b: Now it's time to encode the 'y' coordinate in unary. The dash is advanced like a cursor, adding a 'y' when crossing a number. Since there's a single dash before the first line, two before the second, and so on, that'll be the number of 'y's before each number on each line. next: This is where we remove [-%], the nodes with 0, the numbers and convert them into |<x*y*> format, ie: 101 -> |<xy>|<xxxy>. c: This is the most interesting part of the program. We use the '|' to separate each strongly connected component, with each <x*y*> node initially placed in a different component. Then we move the nodes from different blocks whose coordinate differ in only one x or one y into the same block. Since all this transformation only moves the rightmost node to the component on the left, after a finite number of applications there will be no more possible moves, and we will have converged into the correct grouping. Homework 1 (easy): Prove it ends in finite time. Homework 2 (hard): Prove that anytime it ends it's because it's found the correct (unique-except-by-order) solution. next: Before each pipe we add a '-', using the same technique as in the 'y' coordinate, we end up with |x<node>...|xx<node>...|xxx<node>... next: Time to begin the unary to decimal conversion, we separate the x* and y* with a comma in the middle, and convert the 'y's into 'x's to simplify. e: The unary conversion is pretty straight forward: We add any leading zeros on the |x <x ,x cases. Then 0x is 1, 1x is 2, and so on. For the carry 9x is converted to x0, eg: 19x -> 1x0 -> 20. Any leading zeros are added as needed. Finally there's the conversion to "Isla N: (y,x) (y,x)..." format.