function W = solver(B)

B_orig=B;

%find numbers
nums=unique(B);
nums=nums(2:end)';
len=length(nums);

%find number of occurences
weights=zeros(1,len);
for a=1:len
    weights(a)=nnz(B==nums(a));
end
% weights
wnums=nums.*weights;
[temp idx]=sort(wnums,2,'descend');

nums=nums(idx);
weights=weights(idx);

s=size(B);

W = zeros(s(1)*s(2),4);
wi=1;


grp_list=cell(1,length(nums));
for n=1:len
    [r c]=find(B==nums(n));

    grp=zeros(s(1),s(2));
    for a=1:length(c)
        grp(r(a),c(a))=a;
    end
    for a=1:length(c)
        pv=a-weights(n)+1:a+weights(n)-1;
        pv=pv(pv>0 & pv<=weights(n));
        for p=1:length(pv)
            p1=a;
            p2=pv(p);
            if grp(r(p1),c(p1))==grp(r(p2),c(p2))
                continue
            end
            [sts B W wi grp]=connect([r(p1) r(p2) r(p2)],[c(p1) c(p1) c(p2)],B,B_orig,W,nums(n),wi,grp,nums(n));
            if sts==0
                [sts B W wi grp]=connect([r(p1) r(p1) r(p2)],[c(p1) c(p2) c(p2)],B,B_orig,W,nums(n),wi,grp,nums(n));
            end
            if ~any(grp~=grp(r(1),c(1)))
                break
            end
        end
    end

    grp_list{n}=grp;
end

[W wi]=unite(B,B_orig,W,wi,grp_list,nums);

W=W(1:wi-1,:);
end

function [sts B W wi grp]=connect(r,c,B_in,B_orig,W_in,n,wi_in,grp_in,val)

B=B_in;
W=W_in;
wi=wi_in;
grp=grp_in;
sts=1;
bridge_cost=0;

for a=1:length(r)-1
    if r(a)==r(a+1)
        %horizontal
        connetch;
        if sts==0 || bridge_cost>val*0.9
            return
        end
    else
        %vertical
        connetcv;
        if sts==0 || bridge_cost>val*0.9
            return
        end

    end
    if sts==2
        break;
    end
end

B=B_in;
W=W_in;
wi=wi_in;
grp=grp_in;

    function connetcv
        sts=1;
        d=1-2*(r(a)>r(a+1));
        for b=r(a):d:r(a+1)-d
            if B_in(b+d,c(a))==0
                %empty
                B_in(b+d,c(a))=n;
                W_in(wi_in,:)=[b c(a) b+d c(a)];
                wi_in=wi_in+1;
                grp_in(b+d,c(a))=grp_in(b,c(a));
            elseif B_in(b+d,c(a))==n && grp_in(b+d,c(a))~=grp_in(b,c(a))
                %same number, another group
                B_in(b+d,c(a))=n;
                W_in(wi_in,:)=[b c(a) b+d c(a)];
                wi_in=wi_in+1;
                grp_in(grp_in==grp_in(b+d,c(a)))=grp_in(b,c(a));
                sts=2;
                return
            elseif B_in(b+d,c(a))>0 && B_in(b+d,c(a))~=n && B_orig(b+d,c(a))==0 && b~=r(a+1)-d && B_in(b+d,c(a))~=B_in(b+2*d,c(a)) && B_orig(b+2*d,c(a))==0
                %bridge
                B_in(b+d,c(a))=-1;
                W_in(wi_in,:)=[b c(a) b+d c(a)];
                wi_in=wi_in+1;
                grp_in(b+d,c(a))=grp_in(b,c(a));
                W_in(wi_in,:)=[b+d c(a) b+d c(a)];
                wi_in=wi_in+1;
                bridge_cost=bridge_cost+25;
            else
                sts=0;
                return
            end
        end
    end

    function connetch
        sts=1;
        d=1-2*(c(a)>c(a+1));
        for b=c(a):d:c(a+1)-d
            if B_in(r(a),b+d)==0
                %empty
                B_in(r(a),b+d)=n;
                W_in(wi_in,:)=[r(a) b r(a) b+d];
                wi_in=wi_in+1;
                grp_in(r(a),b+d)=grp_in(r(a),b);
            elseif B_in(r(a),b+d)==n && grp_in(r(a),b+d)~=grp_in(r(a),b)
                %same number, another group
                B_in(r(a),b+d)=n;
                W_in(wi_in,:)=[r(a) b r(a) b+d];
                wi_in=wi_in+1;
                grp_in(grp_in==grp_in(r(a),b+d))=grp_in(r(a),b);
                sts=2;
                return
            elseif B_in(r(a),b+d)>0 && B_in(r(a),b+d)~=n && B_orig(r(a),b+d)==0 && b~=c(a+1)-d && B_in(r(a),b+d)~=B_in(r(a),b+2*d) && B_orig(r(a),b+2*d)==0
                %bridge
                B_in(r(a),b+d)=-1;
                W_in(wi_in,:)=[r(a) b r(a) b+d];
                wi_in=wi_in+1;
                grp_in(r(a),b+d)=grp_in(r(a),b);
                W_in(wi_in,:)=[r(a) b+d r(a) b+d];
                wi_in=wi_in+1;
                bridge_cost=bridge_cost+25;
            else
                sts=0;
                return
            end
        end

    end
end

function [W wi]=unite(B,B_orig,W,wi,grp_list,nums)

gnum=zeros(1,length(grp_list));
gid=cell(1,length(grp_list));
glen=zeros(length(grp_list),20);
gweight=zeros(length(grp_list),20);

% find group members and group weight
for a=1:length(grp_list)
    gid{a}=unique(grp_list{a});
    gid{a}=gid{a}(2:end);
    gnum(a)=length(gid{a});
    for b=1:gnum(a)
        glen(a,b)=nnz(grp_list{a}==gid{a}(b) & B_orig~=0);
        gweight(a,b)=glen(a,b)*nums(a);
    end
end

% 1. column: largest group
[gweight widx]=sort(gweight,2,'descend');

for a=1:length(grp_list)
    gid{a}=gid{a}(widx(a,1:length(gid{a})));
end

if size(gweight,2)==1
    return
end

% 1. row: largest 2. column
[s ridx]=sort(gweight(:,2),1,'descend');

for a=1:size(gweight,2)
    gweight(:,a)=gweight(ridx,a);
end

gid={gid{ridx}};
grp_list={grp_list{ridx}};
nums=nums(ridx);

% try to connect any element
for a=1:nnz(gweight(:,2))
    [r1 c1]=find(grp_list{a}==gid{a}(1));
    [r2 c2]=find(grp_list{a}==gid{a}(2));

    try_all;
end

    function try_all
        sts=1;
        for p1=1:length(r1)
            for p2=1:length(r2)
                if B(r1(p1),c1(p1)) >0
                    [sts B W wi grp]=connect([r1(p1) r1(p1) r2(p2)],[c1(p1) c2(p2) c2(p2)],B,B_orig,W,nums(a),wi,grp_list{a},gweight(a,2));
                    grp_list{a}=grp;
                end
                if sts>0
                    return
                end
            end

        end
    end

end