Для каждой клетки найдем, сколько минимально ходов понадобится красному коню, чтобы попасть в нее (с помощью bfs из синего коня), и сколько минимально ходов понадобится зеленому коню, чтобы попасть в нее (с помощью bfs из зеленого коня). Для того, чтобы оба коня дошли в эту клетку, понадобиться max из ходов красного и зеленого до нее (сколько самый медленный будет идти, столько времени и затратится). И найдем минимальное из всех этих значений среди всех клеток.

Пример кода на python:
from queue import Queue
r, g = input().split()
r = (ord(r[0]) - ord('a'), int(r[1]) - 1)
g = (ord(g[0]) - ord('a'), int(g[1]) - 1)
red = [[-1 for i in range(8)] for j in range(8)]
green = [[-1 for i in range(8)] for j in range(8)]
red[r[0]][r[1]] = 0
green[g[0]][g[1]] = 0
nei = [(1, 2), (1, -2), (-1, 2), (-1, -2),
       (2, 1), (2, -1), (-2, 1), (-2, -1)]
q = Queue()
q.put(r)
while not q.empty():
    h = q.get()
    for e in nei:
        x = h[0] + e[0]
        y = h[1] + e[1]
        if min(x, y) >= 0 and max(x, y) < 8 and red[x][y] == -1:
            red[x][y] = red[h[0]][h[1]] + 1
            q.put((x, y))
q.put(g)
while not q.empty():
    h = q.get()
    for e in nei:
        x = h[0] + e[0]
        y = h[1] + e[1]
        if min(x, y) >= 0 and max(x, y) < 8 and green[x][y] == -1:
            green[x][y] = green[h[0]][h[1]] + 1
            q.put((x, y))
answ = 1000000000
for i in range(8):
    for j in range(8):
        answ = min(answ, max(red[i][j], green[i][j]))
print(answ)