Ayuda con ejercicio - Algoritmo

Iniciado por _RaSH_, 28 Mayo 2016, 19:51 PM

0 Miembros y 1 Visitante están viendo este tema.

_RaSH_

Buenas, me invitaron a unirme a un sitio web de busquedas laborales para programadores.
La cosa es que para poder ingresar te dan a resolver un ejercicio. el cual plantea lo siguiente:

CitarEl instituto geográfico nacional se encarga de, periódicamente, tomar fotografías aéreas para detectar cambios en el relieve terrestre. Para agilizar esta tarea desean tener una herramienta que, dada una imagen, pueda detectar los bordes de las montañas. Las imágenes son representadas con matrices de números enteros que representan la altura sobre el nivel del mar en metros en una posición determinada. Consideraremos a un estrato como a un conjunto conexo de posiciones de la matriz con misma altura. Para que una parte de la imágen se considere el borde de una montaña debe ser un estrato mínimo local. Esto quiere decir que es un estrato y que no posee ningún estrato vecino con altura menor. Diseñar un algoritmo que, dada una matriz, devuelva otra matriz con 0 en todas sus posiciones excepto en los bordes de las montañas que encuentre.

Mas abajo hay una consola para resolver el ejercicio:

Código (php) [Seleccionar]
<?php
// Para testear tu código en nuestros servidores debes mantener la estructura expuesta abajo.
// Eres libre de crear nuevas funciones/procedimientos.
// Recuerda que el código que escribas podrá ser visto por las empresas a las que te postules.
?>

<?php
// $relieve = [[8, 9, 2, 2, 3, 5], [9, 8, 3, 2, 4, 5], [9, 7, 2, 2, 4, 3], [9, 9, 2, 4, 4, 3], [9, 2, 3, 4, 3, 5]];
// Representación gráfica
// 8 9 2 2 3 5  
// 9 8 3 2 4 5  
// 9 7 2 2 4 3  
// 9 9 2 4 4 3  
// 9 2 3 4 3 5
function encontrar_bordes($relieve){
  
// return [[1, 0, 1, 1, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 1, 1, 0, 1], [0, 0, 1, 0, 0, 1], [0, 1, 0, 0, 1, 0 ]];
}
?>


Entiendo que existe un algoritmo llamado "de Floyd-warshall" segun wikipedia:
CitarEn informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica.

Aclaro que para nada quiero que me den la respuesta o me resuelvan el ejercicio. Asi se pierde el chiste jaja, pero si me gustaria entender, la verdad estoy perdido. No entiendo como deberia recorrer la matriz para poder comparar esos puntos. Veo que es simple, entiendo que deberia poder resolverse con poco codigo, por eso es un algoritmo, pero me mato pensando y no se me ocurre nada

saludos