Вот задача:
КОРОЛЬ
В левом нижнем углу шахматной доски mxn стоит одинокий король. Некоторые ячейки доски запрещены для посещения королем. Король имеет возможность ходить или вправо или вверх (или вправо-вверх) на одну ячейку. Найти количество путей короля в правый верхний угол доски.