Почему BFS более эффективен, чем DFS в этом сценарии?

Question

tldr; Вы начинаете с 3 и хотите закончить с 4. Всегда есть гарантированный путь. Вы можете прыгать только на 1. Вы движетесь как рыцарь, m единиц в одном направлении и n единиц в другом, каждый раз. Какое наименьшее количество прыжков, чтобы добраться до пункта назначения.

Input:
1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0

Вы начинаете с 3 и переходите к 1 в средней верхней части, затем к 4. Каждый прыжок - это 1 единица в одном направлении и 2 единицы в другом. Таким образом, ответ для этого случая - 2. Почему BFS лучше, чем DFS в этой ситуации?

Answer 1

Поиск в ширину гарантированно найдет кратчайший путь от начала до цели, тогда как поиск в глубину - нет.