Условие

Дана прямоугольная доска N×M ( N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски.

При этом конь может ходить следующим образом:

Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.

Примеры

Ввод: 4 4 Вывод: 2

Ввод: 2 3 Вывод: 1

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.math.BigInteger

private fun knightsMove(rowsCount: Int, columnCount: Int): BigInteger {
    val field = Array(rowsCount) { arrayOfNulls<BigInteger?>(columnCount) }

    // Начальная точка, единственный путь
    field[0][0] = BigInteger.ONE

    // Варианты хода коня
    val steps = listOf(
        Pair(-2, -1),
        Pair(-1, -2),
        Pair(1, -2),
        Pair(-2, 1)
    )

    // Рекурсивная функция поиска количества путей
    fun find(i: Int, j: Int): BigInteger =
        steps.sumOf { step ->
            val newI = i + step.first
            val newJ = j + step.second
            return@sumOf if (newI in field.indices && newJ in field[newI].indices)
                field[newI][newJ] ?: find(newI, newJ) else BigInteger.ZERO
        }.also { field[i][j] = it }

    return find(rowsCount - 1, columnCount - 1)
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val (rowsCount, columnCount) = reader.readLine().split(" ").map { it.toInt() }
    
    writer.write(knightsMove(rowsCount, columnCount).toString())
    writer.newLine()
    
    reader.close()
    writer.close()
}