Olimpiada Oaxaqueña de Informática
  • Bienvenido a la Olimpiada Oaxaqueña de Informática
  • Temario
    • Introducción a la Programación
      • Definición de computadora
      • Definición de Sistema Operativo
      • Definición de lenguaje de programación
      • Definición de compilador
      • Sistema Binario y Hexadecimal
      • Operaciones AND, OR, NOT, XOR
      • Definición y ejemplo de algoritmos
      • Representación gráfica de un algoritmo
      • Qué es un pseudocódigo
        • Estructura base y Variables
        • Condicionales y ciclos
      • Configuración e instalación de compilador de C y C++
    • Lenguajes de Programación C y C++
      • Presentación de C y C++ como lenguajes de programación
      • Estructura de un programa en C++
        • Ejemplos de códigos en C++
      • Tipos de datos y variables
      • Entrada y salida de datos STDIN SDTOUT
      • Estructuras de Control y Repetición
      • Introducción a estructuras de datos: arreglos
    • Algoritmos de ordenamiento
      • Bubble Sort
    • Estructuras de datos
      • Pilas (Stack)
    • Paradigmas de Solución de Problemas
    • Gráfos
    • Matemáticas
    • Procesamiento de Cadenas
  • OOI 2019
    • Cursos online
      • Clase 1
      • Clase 2
      • Clase 3
      • Clase 4
      • Clase 5
      • Clase 6
      • Clase 7
      • Clase 8
      • Clase 9
      • Clase 10
      • Clase 11
      • Clase 12
      • Clase 13
      • Clase recursión introductorio
  • OOI 2020
    • Instrucciones para nuevos miembros
    • Cursos introductorios
      • Clase 1
      • Clase 2
      • Clase 3
      • Clase 4
      • Clase 5
      • Clase 6
      • Clase 7
      • Clase 8
      • Clase 9
      • Clase 10
      • Clase 11
      • Clase 12
      • Clase 13
      • Clase 14
      • Clase 15
      • Clase 16
      • Clase 17
      • Clase 18
      • Clase 19
      • Clase 20
      • Clase 21
      • Clase 22
    • Cursos avanzados
      • Temario
      • Sesión 1
      • Sesión 2
      • Sesión 3-4
      • Sesión 5
      • Sesión 6
      • Sesión 7
      • Sesión 8
      • Sesión 9-10
      • Sesión 11
      • Sesión 12
      • Sesión 13
      • Sesión 14
      • Sesión 15
      • Sesión 16
      • Sesión 17
      • Sesión 18
      • Sesión 19
      • Sesión 20
      • Sesión 21
      • Sesión 22
    • Cursos matemáticas discretas
      • Sesión 1
      • Sesión 2
  • OOI 2021
    • Fase 4. Semana 1
  • Misceláneos
    • Complejidad de un algoritmo
    • Tutorial instalación VS Code, compilador y debugger para C++
Powered by GitBook
On this page
  • Curso final de la OOI 2020
  • Sesión 22
  • Temas
  • Ejercicios
  • Quién llega primero
  • Quien llega primero parte 2
  1. OOI 2020
  2. Cursos avanzados

Sesión 22

BFS continuación.

PreviousSesión 21NextCursos matemáticas discretas

Last updated 4 years ago

Curso final de la OOI 2020

Sesión 22

Fecha: 4 de junio de 2020

Temas

  • Continuación BFS

Ejercicios

Quién llega primero

Descripción

Arturo y Damian están en distintos lugares de un laberinto. ¿Quién de los 2 llegará primero a la salida?

Entrada

El laberinto donde A es la posición de Arturo, D la de Damian y S la salida. Ambos se pueden mover solo en 4 direcciones y solo pueden avanzar una casilla a la vez. Solo pueden moverse por casillas libres, indicadas por ., pero no pueden pasar por paredes X.

Salida

Imprime el nombre de quién llega primero y la cantidad de pasos que tiene que dar.

Ejemplo

XXXXXXXXXX
X.....A..X
X...XXXXXX
X.X......X
X.XXXXX..X
X.X...X..X
X.X.S.XX.X
X..X.....X
X.D.X....X
XXXXXXXXXX

Arturo 19
XXXXXXXXXX
X.....A..X
X...XXXXXX
X.X......X
X.XXXXX..X
X.X...X..X
X.X.S.XX.X
X..X.....X
X...X..D.X
XXXXXXXXXX

Damian 5

Quien llega primero parte 2

Basado en el problema anterior, imagina que ahora Damian puede moverse a las 8 casillas adyacentes.

XXXXXXXXXX
X.....A..X
X...XXXXXX
X.X......X
X.XXXXX..X
X.X...X..X
X.X.S.XX.X
X..X.....X
X.D.X....X
XXXXXXXXXX

Damian 3

Video: https://www.youtube.com/watch?v=xdC0fgGnlJY

Representación de movimientos dentro de un laberinto para una DFS y BFS