обхдишь матрицу слева направо сверху вниз
если в ячейке исходной матрицы в этом месте единица, ставишь ноль.
если в ячейке этой матрицы в этом месте ноль, то смотришь на новую матрицу на ячейки сверху, слева слева по диагонали. Выбиаешь максимальную из них, прибавлвяешь один, записываешь в ячейку новой матрицы.
потом смотришь, какое в новой матрице максимальное число.
правда этот вариант не сохраняет направления, но его легко восстановить
это если я нигде не туплю