% Author:  Nick Howe

function W = solder2(B)

[nrow,ncol] = size(B);
xB(1:2:2*nrow,1:2:2*ncol) = B;
[Bi,Bj,Bv] = find(xB);
[xnrow,xncol] = size(xB);
xC = zeros(xnrow,xncol);
xC(Bi+xnrow*Bj-xnrow) = 1:numel(Bv);
%allV = unique(Bv);
%xB(2:2:end,2:2:end) = nan;
%for v = fliplr(allV')
%end;
di = [-1 0 1 0];
dj = [0 -1 0 1];
change = 1;
while change
    change = 0;
    for i = 1:numel(Bi)
        v = xB(Bi(i),Bj(i));
        c = xC(Bi(i),Bj(i));
        up = Bi(i)-find(xB(1:Bi(i)-1,Bj(i)),1,'last'); % up
        left = Bj(i)-find(xB(Bi(i),1:Bj(i)-1),1,'last'); % left
        down = find(xB(Bi(i)+1:end,Bj(i)),1); % down
        right = find(xB(Bi(i),Bj(i)+1:end),1); % right
        s = inf(1,4);
        if ~isempty(up)&(xB(Bi(i)-up,Bj(i))==v)&(xC(Bi(i)-up,Bj(i))~=c)
            s(1) = up;
        end;
        if ~isempty(left)&(xB(Bi(i),Bj(i)-left)==v)&(xC(Bi(i),Bj(i)-left)~=c)
            s(2) = left;
        end;
        if ~isempty(down)&(xB(Bi(i)+down,Bj(i))==v)&(xC(Bi(i)+down,Bj(i))~=c)
            s(3) = down;
        end;
        if ~isempty(right)&(xB(Bi(i),Bj(i)+right)==v)&(xC(Bi(i),Bj(i)+right)~=c)
            s(4) = right;
        end;
        [ms,mi] = min(s);
        if ~isinf(ms)
            xB = connect(xB,Bi(i),Bj(i),Bi(i)+ms*di(mi),Bj(i)+ms*dj(mi));
            c = xC(Bi(i)+ms*di(mi),Bj(i)+ms*dj(mi));
            xC = connect(xC,Bi(i),Bj(i),Bi(i)+ms*di(mi),Bj(i)+ms*dj(mi));
            xC(xC==c) = xC(Bi(i),Bj(i));
            change = 1;
        end;
        %if ~isempty(down)&(xB(Bi(i)+down,Bj(i))==v)
        %    xB = connect(xB,Bi(i),Bj(i),Bi(i)+down,Bj(i));
        %elseif ~isempty(right)&(xB(Bi(i),Bj(i)+right)==v)
        %    xB = connect(xB,Bi(i),Bj(i),Bi(i),Bj(i)+right);
        %end;
    end;
end;
W = convertSol(xB);
end


function W = convertSol(xB)
v = xB(2:2:end,1:2:end);
h = xB(1:2:end,2:2:end);
b = xB(1:2:end,1:2:end);
[vi,vj] = find(v~=0);
[hi,hj] = find(h~=0);
[bi,bj] = find(isinf(b));
W = [vi vj vi+1 vj; hi hj hi hj+1; bi bj bi bj];
end


function xB = connect(xB,r1,c1,r2,c2)
if (r1==r2)
    xB(r1,min(c1,c2):max(c1,c2)) = xB(r1,c1);
elseif (c1==c2)
    xB(min(r1,r2):max(r1,r2),c1) = xB(r1,c1);
end
end