Для каждой клетки подсчитай сколькими способами может добраться Ходжа ,потом подсчитай сколькими способами может добраться его осёл . И количество пересечений в данной клетке равно их произведению. А сам ответ равен сумме этих произведений .

Давайте возьмем произвольный путь от левой верхней клетки до правой нижней. Его можно разбить на две части — путь Ходжи, и путь Осла, выбрав ту клетку из пути, в которой они встретятся. И так как в любом пути количество клеток одинаковое, то ответ это просто длина пути умножить на кол-во таких путей, то есть