Локи и Шахматы

В качестве решения данной задачи предполагалось использовать какую-нибудь структуру данных. Например, дерево отрезков. Поступим следующим образом: для всех строк и столбцов заведем деревья отрезков. Каждый раз, когда нужно сдвинуть пешку в каком-либо направлении, будем находить первую пустую клетку в этом направлении. Это можно сделать так: бинарный поиск по длине отрезка, затем находить сумму в дереве отрезков. Если сумма равна длине отрезка, то сдвигать левую границу, иначе правую. Так же это можно сделать за один спуск. После того, как свободная клетка найдена (если такой нет, то делать ничего не нужно), остается присвоить ноль на предыдущую позицию пешки и единицу на только что найденную свободную клетку.