Matlab 171 bytes
The input should be a 2d matrix, so you would call it like
c([1,1,1,1;0,0,0,0;0,0,0,0;1,1,1,1]) (semicolons start a new row). This function just bruteforces all possible moves, so we get a runtime of
How it is done
This is done by choosing all possible ways to fill another matrix of the same size with ones and zero, this is basically counting in binary wich where each entry of the matrix represents a certain power of 2.
Then we perform the moves on those cells that are 1, this is done by the sum (mod 2) of two two dimensional convolution with an vector of ones of size 1xn and nx1.
Finally we decide if those moves actually produced the desired result, by computing the standard deviation over all entries. The standard deviation is only zeros if all entries are the same. And whenever we actually found the desired result we compare it with the number of moves of previous solutions. The function will return
inf if the given problem is not solvable.
It is actually worth noting that all those moves together generate an abelian group! If anyone actually manages to calssify those groups please let me know.
function M=c(a);n=numel(a);p=a;M=inf;o=ones(1,n);for k=0:2^n-1;p(:)=dec2bin(k,n)-'0';b=mod(conv2(p,o,'s')+conv2(p,o','s'),2);m=sum(p(:));if ~std(b(:)-a(:))&m<M;M=m;end;end
Full version (with the output of the actual moves.)
function M = c(a)
M=inf; %current minimum of number of moves
p(:) = dec2bin(k,n)-'0'; %logical array with 1 where we perform moves
b=mod(conv2(p,o,'same')+conv2(p,o','same'),2); %perform the actual moves
m=sum(p(:)); %number of moves;
if ~std(b(:)-a(:))&m<M %check if the result of the moves is valid, and better
disp('found new minimum:')
disp(M) %display number of moves of the new best solution (not in the golfed version)
disp(p) %display the moves of the new best solution (not in the golfed version)