Puntos alcanzables en un mapa
Un mapa con dos tipos de regiones (por ejemplo, tierra y mar) se puede representar mediante una matriz de ceros y unos.
Para los ejemplos usaremos los mapas definidos por
type Punto = (Int,Int) type Mapa = Array Punto Int mapa1, mapa2 :: Mapa mapa1 = listArray ((1,1),(3,4)) [1,1,0,0, 0,1,0,0, 1,0,0,0] mapa2 = listArray ((1,1),(10,20)) [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0, 1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1, 0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
Definir las funciones
alcanzables :: Mapa -> Punto -> [Punto] esAlcanzable :: Mapa -> Punto -> Punto -> Bool
tales que
- (alcanzables p) es la lista de los puntos de mapa m que se pueden alcanzar a partir del punto p moviéndose en la misma región que p (es decir, a través de ceros si el elemento de m en p es un cero o a través de unos, en caso contrario) y los movimientos permitidos son ir hacia el norte, sur este u oeste (pero no en diagonal). Por ejemplo,
alcanzables mapa1 (1,1) == [(2,2),(1,2),(1,1)] alcanzables mapa1 (1,2) == [(2,2),(1,1),(1,2)] alcanzables mapa1 (1,3) == [(3,2),(3,4),(3,3),(2,3),(2,4),(1,4),(1,3)] alcanzables mapa1 (3,1) == [(3,1)]
- (esAlcanzable m p1 p2) se verifica si el punto p1 es alcanzable desde el p1 en el mapa m. Por ejemplo,
esAlcanzable mapa1 (1,4) (3,2) == True esAlcanzable mapa1 (1,4) (3,1) == False esAlcanzable mapa2 (2,3) (8,16) == True esAlcanzable mapa2 (8,1) (7,3) == True esAlcanzable mapa2 (1,1) (10,20) == False
Nota: Este ejercicio está basado en el problema 10 kinds of people de Kattis.
Soluciones
import Data.Array type Punto = (Int,Int) type Mapa = Array Punto Int mapa1, mapa2 :: Mapa mapa1 = listArray ((1,1),(3,4)) [1,1,0,0, 0,1,0,0, 1,0,0,0] mapa2 = listArray ((1,1),(10,20)) [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0, 1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1, 0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] alcanzables :: Mapa -> Punto -> [Punto] alcanzables mapa p = aux [p] [] where region = mapa ! p (_,(m,n)) = bounds mapa vecinos (i,j) = [(a,b) | (a,b) <- [(i,j+1),(i,j-1),(i+1,j),(i-1,j)] , 1 <= a && a <= m , 1 <= b && b <= n , mapa ! (a,b) == region] aux [] ys = ys aux (x:xs) ys | x `elem` ys = aux xs ys | otherwise = aux (vecinos x ++ xs) (x:ys) esAlcanzable :: Mapa -> Punto -> Punto -> Bool esAlcanzable m p1 p2 = p2 `elem` alcanzables m p1