Врятли моё мнение самое правильно, но так как никто более не отписался, позволю предложить следующее:
Создавая рекурсию «в лоб» мы как бы идем вглубину. Грубая оценка говорит, что порядок будет таков: 4^(R+S), поскольку в одном пути не менее R+S ходов, каждый ход порождает 4 варианта дальнейшего движения.
Можно использовать что-то типа поиска в ширину / Динамическое Программирование: каждой клетке приписать число путей, ведущих от левого верхнего края к ней, и заполнять по принципу от ближней к дальней. База: от первой вершины до себя 1 возможный путь. Переход: если клетку окружают клетки со значениями a1, a2, a3, a4 (не все могут быть определены, их временно зануляем), то значение клетки есть их минимум min(a1,a2,a3,a4). Оканчиваем, когда получим значение для правой нижней. Обход всех клеток потребует R*S шагов, такова же сложность алгоритма.