Cálculo del número de islas rectangulares en una matriz
En este problema se consideran matrices cuyos elementos son 0 y 1. Los valores 1 aparecen en forma de islas rectangulares separadas por 0 de forma que como máximo las islas son diagonalmente adyacentes. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
ej1, ej2 :: Array (Int,Int) Int ej1 = listArray ((1,1),(6,3)) [0,0,0, 1,1,0, 1,1,0, 0,0,1, 0,0,1, 1,1,0] ej2 = listArray ((1,1),(6,6)) [1,0,0,0,0,0, 1,0,1,1,1,1, 0,0,0,0,0,0, 1,1,1,0,1,1, 1,1,1,0,1,1, 0,0,0,0,1,1] |
Definir la función
|
1 |
numeroDeIslas :: Array (Int,Int) Int -> Int |
tal que (numeroDeIslas p) es el número de islas de la matriz p. Por ejemplo,
|
1 2 |
numeroDeIslas ej1 == 3 numeroDeIslas ej2 == 4 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
import Data.Array type Matriz = Array (Int,Int) Int ej1, ej2 :: Array (Int,Int) Int ej1 = listArray ((1,1),(6,3)) [0,0,0, 1,1,0, 1,1,0, 0,0,1, 0,0,1, 1,1,0] ej2 = listArray ((1,1),(6,6)) [1,0,0,0,0,0, 1,0,1,1,1,1, 0,0,0,0,0,0, 1,1,1,0,1,1, 1,1,1,0,1,1, 0,0,0,0,1,1] numeroDeIslas :: Array (Int,Int) Int -> Int numeroDeIslas p = length [(i,j) | (i,j) <- indices p, verticeSuperiorIzquierdo p (i,j)] -- (verticeSuperiorIzquierdo p (i,j)) se verifica si (i,j) es el -- vértice superior izquierdo de algunas de las islas de la matriz p, -- Por ejemplo, -- ghci> [(i,j) | (i,j) <- indices ej1, verticeSuperiorIzquierdo ej1 (i,j)] -- [(2,1),(4,3),(6,1)] -- ghci> [(i,j) | (i,j) <- indices ej2, verticeSuperiorIzquierdo ej2 (i,j)] -- [(1,1),(2,3),(4,1),(4,5)] verticeSuperiorIzquierdo :: Matriz -> (Int,Int) -> Bool verticeSuperiorIzquierdo p (i,j) = enLadoSuperior p (i,j) && enLadoIzquierdo p (i,j) -- (enLadoSuperior p (i,j)) se verifica si (i,j) está en el lado -- superior de algunas de las islas de la matriz p, Por ejemplo, -- ghci> [(i,j) | (i,j) <- indices ej1, enLadoSuperior ej1 (i,j)] -- [(2,1),(2,2),(4,3),(6,1),(6,2)] -- ghci> [(i,j) | (i,j) <- indices ej2, enLadoSuperior ej2 (i,j)] -- [(1,1),(2,3),(2,4),(2,5),(2,6),(4,1),(4,2),(4,3),(4,5),(4,6)] enLadoSuperior :: Matriz -> (Int,Int) -> Bool enLadoSuperior p (1,j) = p!(1,j) == 1 enLadoSuperior p (i,j) = p!(i,j) == 1 && p!(i-1,j) == 0 -- (enLadoIzquierdo p (i,j)) se verifica si (i,j) está en el lado -- izquierdo de algunas de las islas de la matriz p, Por ejemplo, -- ghci> [(i,j) | (i,j) <- indices ej1, enLadoIzquierdo ej1 (i,j)] -- [(2,1),(3,1),(4,3),(5,3),(6,1)] -- ghci> [(i,j) | (i,j) <- indices ej2, enLadoIzquierdo ej2 (i,j)] -- [(1,1),(2,1),(2,3),(4,1),(4,5),(5,1),(5,5),(6,5)] enLadoIzquierdo :: Matriz -> (Int,Int) -> Bool enLadoIzquierdo p (i,1) = p!(i,1) == 1 enLadoIzquierdo p (i,j) = p!(i,j) == 1 && p!(i,j-1) == 0 -- 2ª solución -- =========== numeroDeIslas2 :: Array (Int,Int) Int -> Int numeroDeIslas2 p = length [(i,j) | (i,j) <- indices p, p!(i,j) == 1, i == 1 || p!(i-1,j) == 0, j == 1 || p!(i,j-1) == 0] |