Пусть $$$x_s$$$ и $$$y_s$$$ — номер строки и столбца клетки, в которой находится символ «s», а $$$x_f$$$ и $$$y_f$$$ — тоже самое дли символа «f». Сначала, с помощью dfs проверим, достижимы ли вообще друг из друга эти клетки. Если они достижимы, то мы знаем чётность шагов по горизонтали, которые мы сделаем. Оно совпадает с чётностью числа $$$\big|x_s - x_f\big|$$$. Аналогично, мы знаем чётность числа шагов по вертикали. Тогда если из стартовой вершины достижима вершина, из которой можно сделать ход по горизонтали, и достижима вершина, из который можно сделать ход по горизонтали, то с помощью них мы можем получить любую возможную разность между ходами по горизонтали и вертикали, которые удовлетворяют условиям чётности ходов. Тогда ответом будет чётность числа $$$\big|x_s - x_f\big| + \big|y_s - y_f\big|$$$.
Если же какая-то из этих вершин не достижима, то мы можем ходить либо в пределах одной строки, либо в пределах одного столбца, и тогда ответом является $$$\big|x_s - x_f\big| + \big|y_s - y_f\big|$$$.