Здравствуйте, Аноним, Вы писали:

А>Пожалуйста подскажите идею алгоритма или пример решения похожей задачи. google — не помог.

Жестокое решение выглядит так.

Рассмотрим матрицу J (just) с единственной единичкой — для определённости, в верхнем левом углу.
Найдём, какие ходы нужно сделать, чтобы обнулить такую матрицу.
Построим матрицу G (go), где эти ходы будут отмечены единицами.

Рассмотрим матрицу K с единственной единичкой в позиции (x,y). Она получается из матрицы J оператором прокручивания K = rot(x,y,J).
Очевидно, что матрица ходов H, обнуляющая матрицу K, получается этим же оператором из G: H = rot(x,y,G).

Если исходная матрица M (matrix — К.О.) является суперпозицией однопиксельных матриц: M = rot(x1,y1,J) + rot(x2,y2,J) + ... + rot(xn,yn,J),
то матрица решения S (solution) является суперпозицией соответствующих матриц ходов: S = rot(x1,y1,G) + rot(x2,y2,G) + ... + rot(xn,yn,G)
где + это xor (потому что ход, сделанный дважды, отменяет себя).

Или, то же самое,
M = SUM{x,y} M[x,y]*rot(x,y,J)
S = SUM{x,y} M[x,y]*rot(x,y,G)

Кому хочется, можно выразить оператор прокручивания через матричные операции (разложив его на rotx и roty, для начала) и до конца переписать решение в матричном виде над булевым кольцом (* = and, + = xor).

Дальше осталось сделать две вещи:
— придумать, как выглядит матрица G
— просуммировать единички в матрице S